容斥原理的公式推导

对于容斥原理的最简单的理解就是，把要计算的加上，然后把加多的减掉，然后再把减多的再加回去。这样循环下去就对了。

一个好理解的例子就是一个班上有三个兴趣班（c++，java，pasico），每个人都报了兴趣班。30人报了一个，12人报了两个，3人报了三个，求班上有多少人？这是一道小学题，自然也很简单。ans=30-12+3=21（人）。然后这样为什么是对的呢？我们思考一下30之中把报了两项的人计算了2次，把报了三项的人计算了3次。12中把报了3项的人计算了3次。所以我们用那个加减表示每种人都只计算1次的答案。（可以看图再理解一下）

但是并没有那么简单，因为不可能每道题的系数都是-1和1的交替。要解决更一般性的问题，我们可能要自己推系数，我们重点讲一下推系数的方法。

一般的，由总结的公式得出∑ni=1s(Ci)fi=s(C0)$\sum _{i=1}^{n}s(C_i)f_i=s(C_0)$,其中s(Ci)$s(C_i)$表示所有物品在满足Ci$C_i$情况下的总贡献（一般的计数问题s(Ci)$s(C_i)$ 就是 满足条件Ci$C_i$ 情况的个数）,而fi$f_i$是一个系数，在计算时，我们才能把除答案以外的的贡献消掉。（这是用于计算答案的式子）要对这个公式有一个理解，我们还是举两个例子。

一、（错排问题），一串1−n$1-n$的数列，求对于任意i$i$不在第i$i$位排列的方案数。

对于这个问题，首先我们要构造Ci$C_i$，当然这是很简单的，我们很容易就可以想到：Ci$C_i$表示满足有至少i$i$个不错排数的情况。所以有：∑ni=0Cin∗fi==[n==0]$\sum _{i=0}^n{C}_n^i\ast f_i==[n==0]$。反正第一次看人家推这个式子是懵逼的，为啥s(Ci)$s(C_i)$变成一个组合数了呢？其实仔细推敲一下还是可以理解的。首先，上面的式子和下面是有区别的。也就是说，这俩货都不是一个东西。这个式子是用来计算fi$f_i$的！！！

现在大概能懂了吧，假设有一个恰好有n$n$个不错排数的情况，它在i=0$i=0$时被计算了C0n$C_n^0$次，在i=1$i=1$时被计算了C1n$C_n^1$次，以此类推……因为我们要求的的是错排数列，所以当n≠0$n\ne 0$时是不符合题意的，我们要让它的贡献为0（另：只有n=0$n=0$时，这个排列的贡献为1）。然后可以想到一个n2$n^2$递推fi$f_i$的方法。当然这类fi$f_i$是有规律的，我们打表可知：fi=(−1)i$f_i=(-1{)}^i$。

至此我们把fi$f_i$全部计算出来了，之后我们怎么计算答案呢？这个时候我们就可以使用上面一个公式了。ans=∑ni=1Cin∗(n−i)!∗fi$ans=\sum _{i=1}^n{C}_n^i\ast (n-i)!\ast f_i$。

是不是很神奇呢？

二、（约数问题），给定m$m$个数，统计在[1,n]$[1,n]$中，有奇数个整除它的数的个数。(i$i$属于[1,n]$[1,n]$，若在这m$m$个数里，有奇数个数可以整除i$i$，则ans$ans$++)，m≤15$m\le 15$，n≤1e9$n\le 1e9$。

枚举n$n$的复杂度是n∗m$n\ast m$的，显然会超时，考虑容斥。

枚举m$m$的子集，求lcm$lcm$，有了第一题的经验，我们写出式子：∑ki=0Cin∗fi=[k%2==1]$\sum _{i=0}^k{C}_n^i\ast f_i=[k\mathrm{\%}2==1]$，(奇数时贡献为1)。对于一个约数恰好为k$k$个的数，它在计算至少0个约数的时候计算了C0k$C_k^0$次，在计算至少1个约数时计算了C1k$C_k^1$次，以此类推……

怎么计算答案呢？ans=∑(s∈m)nlcm(s)∗f|s|$ans=\sum (s\in m)\frac{n}{lcm(s)}\ast f|s|$。

其实看懂了也很简单，一般求fi$f_i$的式子含组合数，当然也有可能是一些奇奇怪怪的东西，比如斯特林数什么的。