注：本文参考了这位大佬的博客，详情请移步——
容斥
为什么容斥系数乱七八糟但是最后算出来的答案却是正确的的呢。
以一个常见的容斥系数为例子：\(\sum_{i=1}^nC_n^i(-1)^{i+1}\)
\(=\sum_{i=1}^n(C_{n-1}^{i-1}+C_{n-1}^i)\times (-1)^{i+1}\)
\(=\sum_{i=1}^{n}C_{n-1}^{i-1}\times (-1)^{i+1}+\sum_{i=1}^{n-1}C_{n-1}^{i}\times (-1)^{i+1}\)
\(=\sum_{i=1}^{n-1}C_{n-1}^{i}\times (-1)^{i+2}+C_{n-1}^0+\sum_{i=1}^{n-1}C_{n-1}^{i}\times (-1)^{i+1}\)
\(=1\)
用容斥原理解决错排问题
通项公式：
\(ans[n]=n![\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}]\)emmm，通项公式没有办法快速算，好像也木有什么用。。。。
正难则反，不等于的条件范围很大，不好满足，但是等于确是一个很强的约束，所以我们考虑分别计算出一个位置不满足错排、两个位置不满足错排。。。n个位置不满足错排。
因为我们要求的是错排的个数，所以我们要减去不合法的“一个位置不满足错排”的情况数目，但是减去的同时我们多减了一次“同时两个位置不满足错排”的情况（本来只应该被减一次，但是现在被减去了两次），所以我们要加上。但是这样的话就又多加上了“三个位置不满足错排”的情况。。。。。以此类推，故公式为\(ans[n]=\sum_{i=0}^{n}(-1)^i\times C_n^i\times (n-i)!\)
但是这个玩意儿我们没有办法O(1)地计算，所以继续化简——
\(ans[n]=\sum_{i=0}^{n}(-1)^i\times \frac{n!}{i!(n-i)!} \times (n-i)!\)
\(ans[n]=\sum_{i=0}^n(-1)^i\times \frac{n!}{i!}\)
\(ans[n]=\sum_{i=0}^{n-1}(-1)^i\times\frac{n!}{i!}+(-1)^n\)
\(ans[n]=n*ans[n-1]+(-1)^n\)
容斥都有哪些形式？
组合数形式
比如说，对于至少满足一个条件的计算结果，一般长成这个样子——
\(\sum_{i=1}^{n}C_{n}^i*f(i)\)，其中f(i)是容斥系数，对于上述问题来说是(-1)的i+1次方。 而对于至少满足K个条件的计算结果，则是\(\sum_{i=1}^nC_n^i(f(i)=[n>=k])\)。 看了说，如果我们允许\(n^2\)的复杂度，完全可以让程序帮忙计算这个容斥系数（来一个预处理就够了），一个一个递推即可。斯特林数形式
还不会，咕咕咕，回来补。
莫比乌斯函数形式
还不会，咕咕咕，回来补。
容斥系数怎么找？
emmm....凑系数啊！可以打表也可以反演但是我还不怎么会。。。大家还是去看栋栋大佬的博客吧qwqwq
技巧
- 平方处理【例题 管道取珠】 具体的大家可以去看我的题解——已经更新啦！~~
- 反射法【例题】 给定 S,T,K, 求每次 +1,−1, 用不超过 K 次操作从 S 变成 T 的方 案数. 每一时刻都不能为负.