n个元素组成的集合有\(2^n\)个,现在在这些集合中选出若干个(至少1个)使得它们交集的大小为k,问选法种数. n<=10^6
做得有点麻烦...有点怀疑人生... 如果两种选法中交集中包含的k个元素不同,那么一定是不同的选法.所以可以先确定交集包含哪些元素,于是答案里有一个\(C^{k}_{n}\).接下来我们选的每个集合都必须包含这k个元素.包含这k个元素的集合有\(2^{n-k}\)个,那么从中选出若干个但不能一个都不选的方案数是\(2^{2^{n-k}}-1\). 那么最终答案肯定不是\(C^{k}_{n}(2^{2^{n-k}}-1)\),因为这里面算的方案只是交集至少有k个元素,其中的方案的实际交集大小可以大于k.\(C^{k}_{n}(2^{2^{n-k}}-1)\)算的也不是交集至少k个元素的方案数,因为一个交集元素个数大于k的选取方案在这个式子里不止贡献1.假如一个方案A中交集大小为\(j(j>k)\),那么我们枚举\(C^{k}_{n}\)种选出k个元素作为交集的方式时,如果k个元素都是方案A中j个交集元素中的,那么方案A就会在这里被统计一次,因此方案A对这个式子的贡献为\(C^{k}_{j}\). 设\(g[k]=C^{k}_{n}(2^{2^{n-k}}-1),f[k]\)为交集大小恰好等于k的选取方案数. 那么\(g[k]=\sum^{n}_{i=k}C^{k}_{i}f[i]\) 把\(f[k]\)移项就可以DP了.由此可以得到一个\(O(n^2)\)的暴力DP,从\(f[n]\)到\(f[k]\)依次求解.
现在直接考虑每个\(g[i]\)对\(f[k]\)贡献的系数.假设这个系数是\(h[k][i](k\le i),\)那么\(f[k]=\sum_{i=k}^{n}g[i]\times h[k][i]\) 这个系数也可以暴力DP来计算.显然\(h[i][i]=1\),对于其他情况,\(g[i]\)先对\(f[j]\)作出贡献再从\(f[j]\)贡献到\(f[i]\),于是\(h[k][i]=\sum_{j=k+1}^{i} C_{j}^{k}h[j][i]\) 然后,然后我就不会了,然后,然后我就去看网上的题解,发现题解的式子长得和我推出来的形式差不多,只不过把\(h[k][i]\)换成了\((-1)^{i-k}C_{i}^{k}\).抱着怀疑的心情我写了个暴力DP算这个系数,发现确实是这样...一定要记得数学上来先打表 然后...\(h[k][i]=(-1)^{i-k}C_{i}^{k}\)这个结论是有理有据的,我们可以归纳.\(k=i\)显然成立 否则\(h[k][i]=\sum_{j=k+1}^{i} (-1)\times C_{j}^{k}h[j][i]=\sum_{j=k+1}^{i} C_{j}^{k}\times (-1)^{i-j+1} \times C_{i}^{j}\) 考虑\(C_{i}^{j}\times C_{j}^{k}\)的含义,相当于从i个物品里选出j个,再从j个里选出k个.相当于把i个物品分为三组,分别有\((i-j),(j-k),k\)个.那么也相当于\(C_{i}^{k}\times C_{i-k}^{i-j}\),于是\(h[k][i]=(-1)\times \sum_{j=k+1}^{i} (-1)^{i-j}\times C^{i-j}_{i-k}\times C^{k}_{i}\)\(=(-1)\times \sum_{j=k}^{i} (-1)^{i-j}\times C^{i-j}_{i-k}\times C^{k}_{i}+(-1)^{i-k}\times C^{k}_{i}\)\(\sum_{j=k}^{i} (-1)^{i-j}\times C^{i-j}_{i-k}\)用一下二项式定理,就是\((1-1)^{i-k}\),所以相当于\(h[k][i]=(-1)^{i-k}\times C^{k}_{i}\)这个式子似乎是可以直接容斥搞出来,然而辣鸡liu_runda并不会
#include<cstdio> const int mod=1000000007,maxn=1000005; int fac[maxn],inv[maxn]; int qpow(int a,int x,int M){ int ans=1; for(;x;x>>=1,a=a*1ll*a%M){ if(x&1)ans=ans*1ll*a%M; } return ans; } void init(){ fac[0]=1; for(int i=1;i<maxn;++i)fac[i]=fac[i-1]*1ll*i%mod; inv[maxn-1]=qpow(fac[maxn-1],mod-2,mod); for(int i=maxn-1;i>=1;--i)inv[i-1]=inv[i]*1ll*i%mod; } int C(int n,int m){ return fac[n]*1ll*inv[m]%mod*inv[n-m]%mod; } int main(){ init(); int ans=0; int n,k;scanf("%d%d",&n,&k); int flag=1; for(int i=k;i<=n;++i){ if(flag){ ans=(ans+C(n,i)*1ll*C(i,k)%mod*(qpow(2,qpow(2,n-i,mod-1),mod)-1+mod)%mod)%mod; }else{ ans=(ans-C(n,i)*1ll*C(i,k)%mod*(qpow(2,qpow(2,n-i,mod-1),mod)-1+mod)%mod+mod)%mod; } flag^=1; } printf("%d\n",ans); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7119330.html
相关资源：数据结构—成绩单生成器