转载自：iamxym http://blog.csdn.net/xym_csdn/article/details/54177123
传送门(权限题) 题面： 一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得 它们的交集的元素个数为K，求取法的方案数，答案模1000000007。
吐槽一下，不知道为什么网上的题解都没有超过10行的。。 应该是我太弱了吧，连这种题都不会做 初学容斥原理，把之前做过但并不理解的容斥原理题目又复习了一下，然后来做这道题 之前看到的一些例题都是求“至少为…”的答案，直接套容斥的最初形式就可以了，这道题是”恰好为…“的答案，然而我的一般化容斥形式用的并不熟练…… 受3622的影响，写了一个 O(n2) 的暴力，递推恰好为i的方案数，然后 Cin×(22n−i−1) 减去i在大于i的方案数就可以了 f(i)=Cin×(22n−i−1)−∑j=i+1nCijf(j) 然后我就想做前缀和啥的来优化一下，但化了半天式子发现通过乘除系数和加减常数来算 换一种思路，聪哥让我从方程组系数的角度看待容斥原理 容易发现这个式子 Cin×(22n−i−1) 对交集恰好为j的方案计算了 Cij 次 我们先考虑 i=k 的情况， i=k⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪交集大小为k计算的次数交集大小为k+1计算的次数交集大小为k+2计算的次数交集大小为k+3计算的次数...交集大小为n计算的次数CkkCkk+1Ckk+2Ckk+3Ckn 此时交集大小为k的方案数恰好都被计算了一次，所以就考虑 i=k+1 ，我们要把它的计算次数 Ckk+1 消去，同时它也会对下面的k+2,k+3…n产生影响,就是这个样子 i=k+1⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪交集大小为k计算的次数交集大小为k+1计算的次数交集大小为k+2计算的次数交集大小为k+3计算的次数...交集大小为n计算的次数CkkCkk+1−Ckk+1=0Ckk+2−Ckk+1Ck+1k+2=−Ckk+2Ckk+3−Ckk+1Ck+1k+3=−2Ckk+3Ckn−Ckk+1Ck+1n=−(n−k−1)Ckn=−C1n−k−1 然后在 i=k+2 时又要加上 Ckk+2 i=k+2⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪交集大小为k计算的次数交集大小为k+1计算的次数交集大小为k+2计算的次数交集大小为k+3计算的次数...交集大小为n计算的次数CkkCkk+1−Ckk+1=0Ckk+2−Ckk+1Ck+1k+2=−Ckk+2+Ckk+2=0Ckk+3−Ckk+1Ck+1k+3=−2Ckk+3+Ckk+2Ck+2k+3=Ckk+3Ckn−Ckk+1Ck+1n+Ckk+2Ck+2n=(n−k−2)(n−k−1)2Ckn=C2n−k−1Ckn 所以算到 i=j 时，交集大小为n计算的次数就是 (−1)j−kCj−kn−k−1Ckn 因此最终答案就是 ∑i=kn(−1)i−kCkiCin(22n−i−1) 简单理解一下就是我们从至少选i个的方案中( Cin )中选出k个( Cki )乘下方案数,然后容斥计算就可以了 复杂度可以做到 O(n)
#include<cstdio> #define N 1000000 #define LL long long #define mo 1000000007 using namespace std; int n,k; int f[N+5],inv[N+5],fac[N+5]; main() { scanf("%d%d",&n,&k); fac[0]=1;inv[0]=inv[1]=1; for (int i=1;i<=n;++i) fac[i]=fac[i-1]*(LL)i%mo; for (int i=2;i<=n;++i) inv[i]=(LL)(mo-mo/i)*inv[mo%i]%mo; for (int i=2;i<=n;++i) inv[i]=inv[i]*(LL)inv[i-1]%mo; int sum=0,ans=0,t=2; for (int i=n;i>=k;--i) { sum=(LL)fac[n]*inv[k]%mo*inv[n-i]%mo*inv[i-k]%mo*(t-1)%mo; t=(LL)t*t%mo; if (i-k&1) ans-=sum; else ans+=sum; if (ans>=mo) ans-=mo; if (ans<=-mo) ans+=mo; } printf("%d\n",(ans+mo)%mo); }看到FTD大神的题解，发现还有一种更好理解的想法 我们先从n个集合中选出来k个，这样就是 2n−k−1 个符合条件的非空子集，除去这k个要求为空集，这个容斥起来更加浅显，直接补集转化”总方案数-交集不为空的方案数=总方案数-(交集至少为1的方案数-交集至少为2的方案数…)
#include<cstdio> #define N 1000000 #define LL long long #define mo 1000000007 using namespace std; int n,k; int f[N+5],inv[N+5],fac[N+5]; int C(int m,int n){return (LL)fac[n]*inv[m]%mo*inv[n-m]%mo;} main() { scanf("%d%d",&n,&k); fac[0]=1;inv[0]=inv[1]=1; for (int i=1;i<=n;++i) fac[i]=fac[i-1]*(LL)i%mo; for (int i=2;i<=n;++i) inv[i]=(LL)(mo-mo/i)*inv[mo%i]%mo; for (int i=2;i<=n;++i) inv[i]=inv[i]*(LL)inv[i-1]%mo; int sum=0,ans=0,t=2; for (int i=n-k;i>=0;--i) { sum=(LL)(C(i,n-k))%mo*(t-1)%mo; t=(LL)t*t%mo; if (i&1) ans-=sum; else ans+=sum; if (ans>=mo) ans-=mo; if (ans<=-mo) ans+=mo; } ans=(LL)(ans)*C(k,n)%mo; printf("%d\n",(ans+mo)%mo); }这样做题并不能够满足，我想了另一个扩展（sha bi）问题，求至少为k的方案数 显然之前的 O(n2) 暴力随便做 然后我就想啊想推啊推，顺便问mrazer和聪哥，终于把这个给搞出来了 把 k′=k,k+1,k+2..n 情况下容斥的式子都列出来，然后累加一下，就得到了这个答案 ∑i=kn(22n−i−1)Cin∑j=ki(−1)i−jCji
结合杨辉三角我们发现式子可以写成这样 ∑j=ki(−1)i−jCji=(−1)i−k(Ck−1i−1+Cki−1)+(−1)i−k+1(Cki−1+Ck+1i−1)+..(−1)0(Ci−1i−1+Cii−1)=(−1)i−kCk−1i−1 所以答案就是这个 ∑i=kn(−1)i−kCk−1i−1(22n−i−1)Cin 貌似是zz问题？ 但我并不会从容斥的角度来解释这个式子TAT 如果有大神知道请留言……
#include<cstdio> #include<iostream> #define N 1000000 #define LL long long #define mo 1000000007 using namespace std; int n,k; int f[N+5],inv[N+5],fac[N+5]; int C(int m,int n){return (LL)fac[n]*inv[m]%mo*inv[n-m]%mo;} main() { scanf("%d%d",&n,&k); fac[0]=1;inv[0]=inv[1]=1; for (int i=1;i<=n;++i) fac[i]=fac[i-1]*(LL)i%mo; for (int i=2;i<=n;++i) inv[i]=(LL)(mo-mo/i)*inv[mo%i]%mo; for (int i=2;i<=n;++i) inv[i]=inv[i]*(LL)inv[i-1]%mo; int sum=0,ans=0,t=2,flag; for (int i=n;i>=k;--i) { flag=(i+k&1?-1:1); sum=(LL)flag*C(k-1,i-1)*C(i,n)%mo*(t-1)%mo; t=(LL)t*t%mo; ans+=sum; if (ans>=mo) ans-=mo; if (ans<=-mo) ans+=mo; } printf("%d\n",(ans)%mo); }