2839: 集合计数
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 399 Solved: 217Description
一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）Input
一行两个整数N,KOutput
一行为答案。Sample Input
3 2Sample Output
6HINT
【样例说明】
假设原集合为{A,B,C}
则满足条件的方案为：{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}
【数据说明】
对于100%的数据，1≤N≤1000000；0≤K≤N；
【分析】
我的容斥好垃圾哦。。。
答案=至少交集为k-至少交集为k+1+至少交集为k+2
注意‘至少’的意义。如若不是，那么是不需要容斥的。而是答案=至少交集为k-交集为k+1-交集为k+2-交集为k+3。。。
算‘至少’好算多了，你只要保证了有k个，后面的东西都随便了。
从n个数中选出k个作为交集中的数,是C(n,k)，这样的集合共有2^(2^(n-k))-1个
2^(n-k)是包含选定的k个数的可选集合的数量，选取方案有2^(2^(n-k))-1个(不能有空集否则无法保证k个元素)
所以ans=C(n,k)*C(k,k)*(2^(2^(n-k))-1)-C(n,k+1)*C(k+1,k)*2^(2^(n-k-1)
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define LL long long 8 #define Maxn 1000010 9 const int Mod=1000000007; 10 11 int pw[Maxn],inv[Maxn],tpw[Maxn]; 12 13 void init(int n) 14 { 15 // tpw[0]=1;for(int i=1;i<=n;i++) tpw[i]=1LL*tpw[i-1]*2%Mod; 16 pw[0]=1;for(int i=1;i<=n;i++) pw[i]=1LL*pw[i-1]*i%Mod; 17 inv[1]=1;for(int i=2;i<=n;i++) inv[i]=1LL*(Mod-Mod/i)*inv[Mod%i]%Mod; 18 inv[0]=1;for(int i=1;i<=n;i++) inv[i]=1LL*inv[i-1]*inv[i]%Mod; 19 } 20 21 int qpow(int x,int b,int p) 22 { 23 int ans=1; 24 while(b) 25 { 26 if(b&1) ans=1LL*ans*x%p; 27 x=1LL*x*x%p; 28 b>>=1; 29 } 30 return ans; 31 } 32 33 int get_c(int n,int m) 34 { 35 return 1LL*pw[n]*inv[n-m]%Mod*inv[m]%Mod; 36 } 37 38 int f[Maxn]; 39 int main() 40 { 41 int n,k,ans=0; 42 scanf("%d%d",&n,&k); 43 init(n); 44 for(int i=n;i>=k;i--) 45 { 46 f[i]=1LL*(qpow(2,qpow(2,n-i,Mod-1),Mod)-1)*get_c(n,i)%Mod*get_c(i,k)%Mod; 47 } 48 for(int i=k+1;i<=n;i++) 49 { 50 if((i-k)&1) f[k]-=f[i]; 51 else f[k]+=f[i]; 52 f[k]%=Mod; 53 } 54 f[k]=(f[k]+Mod)%Mod; 55 printf("%d ",f[k]); 56 return 0; 57 }
2017-04-19 10:44:21