容斥原理
(|A_1cup A_2cup...cup A_n|=sumlimits_{1le ile n}|A_i|-sumlimits_{1le i<jle n}|A_icap A_j|+...+(-1)^{n-1} imes |A_1cap A_2cap ...cap A_n|)
二项式反演
形式1
(f_i=sum_{j=k}^n C(i,j)*g_j Leftrightarrow g_i=sum_{j=k}^n (-1)^{i-j}*C(i,j)*f_j)
形式2
(f_i=sum_{j=k}^n (-1)^j*C(i,j)*g_j Leftrightarrow g_i=sum_{j=k}^n (-1)^j*C(i,j)*f_j)
证明1
(|A_1cup A_2cup...cup A_n|=sumlimits_{1le ile n}|A_i|-sumlimits_{1le i<jle n}|A_icap A_j|+...+(-1)^{n-1} imes |A_1cap A_2cap ...cap A_n|)
(Rightarrow |complement A_1cap complement A_2cap...cap complement A_n|=|S|-sumlimits_{1le ile n}|A_i|+sumlimits_{1le i<jle n}|A_icap A_j|-...-(-1)^{n-1} imes |A_1cap A_2cap ...cap A_n|)
(Rightarrow |A_1cap A_2cap...cap A_n|=|S|-sumlimits_{1le ile n}|complement A_i|+sumlimits_{1le i<jle n}|complement A_icap complement A_j|-...-(-1)^{n-1} imes |complement A_1cap complement A_2cap ...cap complement A_n|)
假设现在交集的大小仅是关于集合个数的函数,
设(f_n)表示(|A_1cap A_2cap...cap A_n|),(g_n)表示(|complement A_1cap
complement A_2cap...cap complement A_n|),且(f(0)=g(0)=|S|),则
(f_i=sum_{j=0}^i (-1)^j*C(i,j)*g_j)
(g_i=sum_{j=0}^i (-1)^j*C(i,j)*f_j)
形式2得证,证明形式1只需代换即可.
对于(sum_{j=k}^i)的情况,请看证明2.
证明2
对于形式1,把(f_i)代入右侧式子得
(g_i=sum_{j=k}^i (-1)^{i-j}*C(i,j)*sum_{l=k}^j C(j,l)*g_l)
(=sum_{l=k}^i sum_{j=l}^i (-1)^{i-j}*C(i,j)*C(j,l)*g_l)
(=sum_{l=k}^i sum_{j=l}^i (-1)^{i-j}*frac{i!}{j!(i-j)!}*frac{j!}{l!(j-l)!}*g_l)
(=sum_{l=k}^i sum_{j=l}^i (-1)^{i-j}*frac{(i-l)!}{(i-j)!(j-l)!}*frac{i!}{(i-l)!l!}*g_l)
(=sum_{l=k}^i C(i,l)*g_l*sum_{j=l}^i (-1)^{i-j}*C(i-l,j-l))
当(i
eq l)时,由二项式定理,得(sum_{j=l}^i (-1)^{i-j}*C(i-l,j-l)=(1-1)^{i-l}=0)
当(i=l)时,(sum_{j=l}^i (-1)^{i-j}*C(i-l,j-l)=1)
( herefore g_i=[i=l]*C(i,l)*g_l=g_i),得证.
习题
A. HDU 4135
求 ([A,B]) 中有多少个数与 (N) 互质。 (A,Ble 10^{15},Nle 10^9)
解
(O(sqrt n)) 找出 (n) 的所有质因子，然后指数级容斥。可以证明质因子个数不会超过15个。
B. HDU 4059
(Tle 1000) 组询问，给定 (n) ，求与 (n) 互质的数的四次方和。
解
(O(sqrt n)) 找出 (n) 的所有质因子，然后指数级容斥。可以证明质因子个数不会超过6个。
C. HDU 5201
有 (n) 件物品， (m) 个人，现在要把物品分给人，要求没有一个人拿到的物品数大于等于第一个人拿到的物品数。求方案数。多组数据。 (Tle 25,n,mle 10^5)
解
先枚举第一个人拿到的物品数 (i)。
然后就要求把 (n-i) 个物品分给 (m-1) 个人且每个人不能超过 (i) 的方案数。