神秘场。
\(0+100+70\) 不会做 T1 遗憾离场了。不过为啥 hxq 和 yjh 不会 T2。
排列(perm)
原题
首先考虑容斥。记 \(dp_x\) 表示选出 \(x\) 个位置不满足限制的方案数。如果我们已经知道了 \(dp_x\) 那么我们可以通过容斥：
\[ans=\sum dp_x\times (-1)^k(n-k)!
\]
轻松算出答案。难点在于如何算 \(dp_x\)。
赛时想到了考虑图论建模。在 \(i\) 相同的 \((p_i,q_i)\) 间连边。然后就是一个点覆盖问题。
但是我不会一般图点覆盖。所以我赛时就不会了。
然而实际上你考虑我们这个图由于是由两个排列中的点构成的，度数 \(=2\) 且仅仅会包含环。（原题中有自环，但是搬题人很好心的吧自环去了）。
考虑环怎么做。你发现直接在环上做基本做不了。直接短环成链分讨一下。
令 \(f_{i,j}\) 表示在一个长度为 \(i\) 的链上选 \(j\) 条边的方案数，\(g_{i,j}\) 表示在一个长度为 \(i\) 的环上选 \(j\) 条边的方案数。
我们在断环成链之后考虑如果我们不选被断掉的这条边，那么方案数就应该是 \(f_{i,j}\)。
如果选了这个被断掉的边，那么这时候就和首尾的点有关了。
令 \(w_{i,j,0/1,0/1}\) 表示在一个长度为 \(i\) 的链上