如果有错误，欢迎打脸
（由于太懒还没）同步于我的博客
有时候我们要按照类别来统计数量，可能有的元素属于多个不同的类别。在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，可以利用容斥原理。
一些前置技能
二项式定理
\sum_{i=0}^{n}{n \choose i}a^ib^{n-i}=(a+b)^n
交换求和号
这个不太好描述……具体问题具体分析……就举个例子……
\sum_{i=0}^{n} f(i) \sum_{j=0}^{i} g(j)h(i,j)=\sum_{j=0}^{n} g(j) \sum_{i=j}^{n} f(i)h(i,j)
交换后只要保证每一组乘积与之前一一对应即可
组合数经典公式
{n \choose i}={n-1 \choose i}+{n-1 \choose i-1}
公式化的理解：手动拆开式子然后约分
从组和数上的意义理解：从n个物品中挑选出i个物品，相当于考虑是否最终挑选出第i个物品，如果不挑选出，那么方案数为{n-1 \choose i}，如果挑选出，那么方案为{n-1 \choose i-1}
这个公式十分有用……如果是一个组合数乘上一个-1的若干次幂后求和的形式，可以直接大力拆式子，然后一正一负就消掉了……
参考文献
WerKeyTom_FTD 《容斥的原理及广义应用》
什么是容斥
从一个简单的例题说起
有k种属性，你有一个函数f(S)，可以快速得知至少满足S属性的集合的物品个数，同时定义f(\emptyset)=0
现在你想知道至少有一种属性的物品的个数，k \le 20
可能小学老师们告诉过你，答案就是
\sum_{S \subseteq U}f(S)(-1)^{|S|+1}
通过文氏图，可以轻而易举的得知在k \le 3的时候是十分清晰易懂的，那么在k更高维的情况下，不妨证明一下为什么这个式子是对的
考虑每一个物品，假设它有n个属性，当然在n=0的时候只会被f(\emptyset)枚举到，而且对答案的贡献为0
如果n \ge 1，那么可以枚举一下它的属性会被哪些组合枚举到，既
\begin{aligned}\sum_{i=1}^{n} {n \choose i} (-1)^{i+1}&=-(\sum_{i=1}^{n} {n \choose i} (-1)^{i})\\&=-((1-1)^n-1)\\&=1\end{aligned}
因此这个物品如果至少有一个属性的话那么一定会被只对答案产生1的贡献
也许对容斥有了一些感性的理解了吧
一般化的经典容斥
首先需要有一个属性集合k，然后假设有一个可以查询至少满足属性集合S的物品个数的函数q(S)
同时还有一个函数g(k)，对于一个有k个属性的物品，它会对答案产生g(k)的贡献
同时确定一个容斥系数f(x)，使得答案为\sum_{S \subseteq U}q(S)f(|S|)
此时看一下每一个物品会怎么对答案产生贡献的（假设这个物品有n个属性）：
\sum_{i=1}^{n} {n \choose i} f(i)=g(n)
如果允许O(n^2)的时间复杂度的话，可以直接通过递推来计算出f(x)
既假设知道了f(1) \sim f(n)，现在要计算f(n+1)，根据定义有
\sum_{i=1}^{n+1} {n + 1 \choose i} f(i)=g(n+1) \Rightarrow f(n+1)=g(n+1)-\sum_{i=1}^{n} {n+ 1\choose i} f(i)
于是就可以打表找规律了！
计算容斥系数
然而如果需要快速计算f(x)呢？
发现上面那个式子比较像卷积的形式，定义f(0)=0
也就是说
\begin{aligned}g(n)&=\sum_{i=1}^{n} {n \choose i} f(i) \\&=\sum_{i=0}^{n}\frac{n!}{i!(n-i)!}f(i) \\&=n!\sum_{i=0}^{n}\frac{1}{(n-i)!}\frac{f(i)}{i!} \\\end{aligned}
整理一下就是
\frac{g(n)}{n!}=\sum_{i=0}^{n}\frac{1}{(n-i)!}\frac{f(i)}{i!}
设G(x)=\sum\limits_{i=0}^{\infty}x^i\frac{g(i)}{i!},H(x)=\sum\limits_{i=0}^{\infty}x^i\frac{1}{i!}=e^x,F(x)=\sum\limits_{i=0}^{\infty}x^i\frac{f(i)}{i!}
则G(x)=H(x)F(x)，也就是F(x)=\frac{G(x)}{H(x)}=e^{-x}G(x)
于是可以用优秀的多项式求逆算法在O(n \log n)的时间复杂度内解决了！
当然还有一种优秀的反演方法……并没有学会……
可以在WerKeyTom_FTD 《容斥的原理及广义应用》中看到
一些简单的应用
统计人数问题
已知在某场比赛中，一共有\{1,2,3\}这三道题，同时你可以查询f(S)，会返回至少切了集合S的题的人的个数，问有多少人至少切了一道题？
根据上面的推导，可以知道答案就是
f(\{1\})+f(\{2\})+f(\{3\})-f(\{1,2\})-f(\{1,3\})-f(\{2,3\})+f(\{1,2,3\})
错排问题
问1 \sim n的所有排列a中，满足a_i \not= i的排列数
对于不等于的限制似乎不太好做，但对于等于的限制是十分好做的：如果有x个位置满足a_i=i，那么其余位置的方案数为(n-x)!
所以可以枚举至少哪些位置是不合法的，然后容斥一下
设f(n)表示n个数的错排个数，则
\begin{aligned} f(n) &=\sum_{i=0}^{n}(-1)^{i} {n \choose i} (n-i)! \\ &=\sum_{i=0}^{n}(-1)^i \frac{n!}{i!(n-i)!}(n-i)! \\ &=\sum_{i=0}^{n}(-1)^i \frac{n!}{i!} \\ &=n\sum_{i=0}^{n}(-1)^i \frac{(n-1)!}{i!} \\ &=(-1)^{n} \frac{n!}{n!} + n\sum_{i=0}^{n-1}(-1)^i \frac{(n-1)!}{i!} \\ &=(-1)^{n} + nf(n-1) \\ \end{aligned}
关于第一行的说明：
首先需要枚举一下有多少个位置是不满足错排的，这个是\sum_{i=0}^{n}
其次需要一个容斥系数，为(-1)^i
之后枚举那些位置不满足错排，这是{n \choose i}
对于剩下的位置可以随意放，也就是(n-i)!
证明一下正确性：
假设一个排列有k的地方满足a_i = i，既要求对答案的贡献为[k=0]
那么实际对答案的贡献为：
\begin{aligned} \sum_{i=0}^{k}{k \choose i}(-1)^i \end{aligned}
上面那个式子在k=0的时候对答案的贡献为1，满足题意，以下考虑在k \ge 1的情况下对答案的贡献
\begin{aligned} \sum_{i=0}^{k}{k \choose i}(-1)^i &=(1-1)^k\\&=0\end{aligned}
那如果要求恰好k个位置满足错排呢？
枚举一下哪些位置不满足错排，显然剩下的位置只能唯一确定，既{n \choose k}f(k)
那如果要求至少k个位置满足错排呢（k \ge 1）？
同理，答案就是\sum_{i=1}^{k} {n \choose i}f(i)
方程的解问题
给定一个方程\sum_{i=1}^{n}x_i=b，问非负整数的个数
通过组合数学，可以得知解的个数为{n+b-1 \choose n-1}
一个简单粗暴的证明：
相当于将b个1分割成n份，允许某份是空的，问方案数
考虑设置n个特殊点，如果第i个特殊点被选中了，则第i堆为空
然后将b个1分成若干份，依次对应非空的x_i
于是解的个数就是{n+b-1 \choose n-1}
然而如果对于每一个x_i都有限制呢？诸如l_i \le x_i \le r_i
设y_i=x_i-l_i，也就是0 \le y_i \le r_i-l_i，这样对于每一个非负整数解y_i，都有一个非负整数x_i与之对应
换句话说问题转化为了限制诸如0 \le x_i \le k_i的形式
考虑容斥，每次枚举哪些x_i不满足限制，既x_i \ge k_i+1，然后配上正确的容斥系数
如何让x_i不满足限制？设x_i'=x_i+k_i+1，然后把x_i'替换x_i就行了
设f(S)表示集合S的变量不满足限制的方案数，显然有
f(S)={n+b-1-\sum_{i \in S}(k_i+1)\choose n-1}
同时对于答案T，有
T=\sum_{S \subseteq U}(-1)^{|S|}f(S)=\sum_{S \subseteq U}(-1)^{|S|}{n+b-1-\sum_{i \in S}(k_i+1)\choose n-1}
字符串匹配问题
SDOI2009 Bill的挑战
有n个长度相同的模板串，用?表示通配符（可以匹配任何字符），给出一个整数k，求恰好匹配k个模板串的字符串的个数
一般化的题目描述：
有n个属性，求恰好满足k个属性的物品个数
你有一个函数q(S)，可以快速算出至少满足属性集合S的物品个数（保证每个物品最多只会被统计一次）
设f(S)表示只满足属性集合S的物品的个数，那么答案就是\sum_{S \subseteq U \wedge |S| = k}f(S)
设f(S)=\sum\limits_{S \subseteq P \subseteq U}q(P)g(|P|)，其中|S|=k，显然有g(x)=(-1)^{x-k}
证明：
对于一个物品t，假设它的属性集合为Q，且S \subseteq Q，且|Q|=k+u
那么它对f(S)的贡献是
\sum_{i=0}^{u}{u \choose i}(-1)^{i}=(-1+1)^{u}=[u=0]
也就是说f(S)=\sum\limits_{S \subseteq P \subseteq U}q(P)(-1)^{|P|-k}
也就是说
\begin{aligned}T&=\sum\limits_{S \subseteq U \wedge |S| = k}f(S) \\&=\sum\limits_{S \subseteq U \wedge |S| = k} \sum_{S \subseteq P \subseteq U}q(P)(-1)^{|P|-k} \\&=\sum\limits_{P \subseteq U \wedge |P| \ge k} q(P)(-1)^{|P|-k}{|P| \choose k}\end{aligned}
于是就做完了……
q(S)$的话可以直接判断一下是否有冲突，如果没有冲突的话求一下有多少个位置是用`?`填充的，假设有$x$个位置用`?`填充，那么$q(S)=2^x
如果扩展一下这道题，将“恰好”改成“至少”呢？
设T(k)表示恰好匹配k个字符串的方案数，Q(k)表示至少匹配k个字符串的方案数，则
\begin{aligned} Q\left(k\right) &=\sum_{i=k}^{n}T\left(i\right) \\ &=\sum_{i=k}^{n}\sum\limits_{P \subseteq U \wedge |P| \ge i} q\left(P\right)\left(-1\right)^{|P|-i}{|P| \choose i} \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\sum_{i=k}^{|P|}\left(-1\right)^{|P|-i} {|P| \choose i} \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{1-|P|}\sum_{i=k}^{|P|}\left(-1\right)^{i} {|P| \choose i} \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{1-|P|}\sum_{i=k}^{|P|}\left(-1\right)^{i} \left({|P| - 1 \choose i}+{|P| -1 \choose i-1}\right) \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{1-|P|}\left(\left(\sum_{i=k+1}^{|P|+1}\left(-1\right)^{i-1} {|P| - 1 \choose i-1}\right)+\left(\sum_{i=k}^{|P|}\left(-1\right)^{i}{|P|-1 \choose i-1}\right)\right) \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{1-|P|}\left(\left(-1^{|P|}\right){|P|-1 \choose |P| }+\left(-1\right)^{k}{|P|-1 \choose k-1}\right) \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{|P|-k}{|P|-1 \choose k-1} \\ &=\sum_{P \subseteq U \wedge |P| \ge k} q\left(P\right)\left(-1\right)^{|P|-k}{|P|-1 \choose |P|-k} \\ \end{aligned}
这个似乎没什么解释的……将一个式子套到另一个式子后，直接化简……
鸣谢