【BZOJ 2839】 2839: 集合计数（容斥原理）-白红宇

【BZOJ 2839】 2839: 集合计数（容斥原理）

阅读量：5337 次

发布时间：2019-06-15

本文共 2101 字，大约阅读时间需要 7 分钟。

2839: 集合计数

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 399  Solved: 217

Description

一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得

它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）

Input

一行两个整数N,K

Output

一行为答案。

Sample Input

3 2

Sample Output

6

HINT

【样例说明】
假设原集合为{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
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             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\n",f[k]);56     return 0;57 }