错位排列
对于 1\sim n 的排列 P 如果满足 P_i\neq i ，则称 P 是 n 的错位排列。求 n 的错位排列数。
递推式：
假设前 n-1 个已经放好，第 P_n 位置放了 n。如果前 n-1 个已经是错位排序，则将 P_n 与前面任意一个交换，可以产生一个 n 的错位排序；如果前面只有 1 个不是错位，则将其与 P_n 交换，也可产生错位排序。因此：
f(n)=(n-1)(f(n-1)+f(n-2))
公式：
\begin{aligned}
Ans&=n!-\binom{n}{1}\cdot (n-1)! +\binom{n}{2}\cdot(n-2)!-\cdots\cr &=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}
\end{aligned}
例题：CF340E Iahub and Permutations
有一个长度为 n 的排列 a，其中有一些位置被替换成了 -1。你需要尝试恢复这个排列，将 -1 替换回数字。 求多少种可行方案使得得到的是一个排列且不存在 a_i=i 的位置。
分析：假设有 num 个 -1；在所有 -1 中，有 cnt 个数可能对应到相同的编号。考虑上面的容斥定理，答案为：
\sum_{i=0}^{cnt}\binom{cnt}{i}\cdot (num-i)!
相同数不能相邻的排列数
设集合 S=\begin{Bmatrix}1,1,2,2,\cdots,n,n\end{Bmatrix}，求相同数不能相邻的排列数。
分析：
考虑容斥。
至少有一对相邻的排列数：\binom{n}{1}\cdot \frac{(2n-1)!}{2^{n-1}}；
至少有两对相邻的排列数：\binom{n}{2}\cdot \frac{(2n-2)!}{2^{n-2}}
……
Ans=\sum_{k=0}^{n}\binom{n}{k}\cdot \frac{(-1)^{n-k}\cdot (n+k)!}{2^k}
递推式：
a(n) = n(2n-1)\cdot a(n-1) + n(n-1)\cdot a(n-2)
例题
题目大意：
有 n 个家庭，每个家庭有 a_i 个男孩和 b_i 个女孩。满足 \sum{a_i}=\sum{b_i}<1e5 。不允许近亲结婚。问一共有多少种满足要求的两两配对方案。
解题思路：
考虑第 i 个家庭至少有 x 对近亲的方案数：
\binom{a_i}{x}\cdot \binom{b_i}{x}\cdot x!
我们可以很方便得到其生成函数。将每个家庭的生成函数相乘，可以得到全部家庭的生成函数 F。考虑容斥定理，最终的答案为：
F(0)-F(1)+F(2)-\cdots
int main() {
init(); // 处理C函数
int T; scanf("%d", &T);
while (T--) {
scanf("%d", &n);
vector<VI> all;
int sum = 0;
for (int i = 0, a, b; i < n; i++) {
scanf("%d%d", &a, &b);
sum += a;
int up = min(a, b);
VI now;
for (int i = 0; i <= up; i++) {
int x = 1LL * C(a, i) * C(b, i) % P * fac[i] % P;
now.push_back(x);
}
all.push_back(now);
}
VI ans = multiply_all(0, all.size() - 1, all);
int res = 0;
for (int i = 0; i < SZ(ans); i++) {
int tmp = 1LL * ans[i] * fac[sum - i] % P;
if (i & 1) (res += P - tmp) %= P;
else (res += tmp) %= P;
}
printf("%d\n", res);
}
return 0;
}