集合计数-容斥原理

内存限制：128 MiB 时间限制：1000 ms 标准输入输出

一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）

一行两个整数N,K

一行为答案。

样例输入

3 2

样例输出

样例说明

假设原集合为{A,B,C}

则满足条件的方案为：{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}

数据说明

对于100%的数据，1≤N≤1000000；0≤K≤N；

这题首先一看一脸懵，思路就是先找出n个元素中的k个元素，那么就是C（n，k）;然后就是在剩下的元素的选出任意多个集合，使他们的这些集合各自交集为空;

那么我们就枚举这些集合的交集中比k个元素多x个元素，然后设i=k+x进行计算;

那么从n元素中选出i个元素之后，就剩下n-i个元素，这些元素可以组成2^(n-i)个集合;这些集合可以有两种方案，一种是选，一种是不选，所以就需要有（2^（2^(n-i)）-1）种情况

但是我们又不能在这些集合中一个都不选，所以所有情况的基础上都要-1;

那么我们就可以推出一个公式：

　　C(n,i)*(2^(2^(n-i))-1)*C(i,k)我们不妨吧这个式子定义为q（i）;

那么我们就手%一下样例：（题里的样例不太具有代表性，我们不妨设n==4，k==2时）让我们来%一下：

q（2）=C（4，2）*（2^(2^(2))-1）*C(2,2)=6*15*1=90;

q(3)=C(4,3)*(2^2)*C(3,2)=4*3*1=12;

…………;

但是通过手动枚举这些集合就可以发现，其实这些集合并不是严谨的交集是k，所以我们要减去交集是k+1的，但是交集是k+1的他们的交集我们这个式子求出来的又多减去了k+2的

就要加上k+2的，以此类推就是容斥原理

具体实现：

1 for(LL i=k;i<=n;i++,zt=-zt)
2         ans+=((C(n,i)*(1ll*qpow(2,tpower[n-i],p)-1))%p*C(i,k)*1ll)%p*zt*1ll;

容斥部分

其实一开始我的代码是这样的：

1 for(int i=k;i<=n;i++,zt=-zt)
2         ans+=((C(n,i)*(qpow(2,qpow(2,n-i,p-1),p)-1))%p*C(i,k))%p*zt;

TLE

那么很明显差异就在我打了一个2^n的表qwq！

然后改完以后就不TLE了变成了WA70，为什么？

在我的不懈改题下，终于在无数次的失败过后发现，把（ans+p）%p就AC了;

一刀干死我吧！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 #define LL long long
 6 const int p=1e9+7;
 7 const int N=1001000;
 8 LL n,sz[N],k;
 9 LL inv[N],jc1[N],jc2[N],tpower[N];
10 LL dp[N];
11 LL ans;
12 LL C( LL n, LL m)
13 {
14     if(n<m)return 0;
15     if(!m||m==n)return 1;
16     if(n>p||m>p)
17         return (C(n%p,m%p)*C(n/p,m/p))%p;
18     else return ((jc1[n]*jc2[m])%p*jc2[n-m])%p;
19 }
20 LL qpow(LL x,LL m,LL mod)
21 {
22     if(m==0)
23         return 1;
24     LL tmp=qpow(x,m/2,mod);
25     tmp=(tmp*tmp)%mod;
26     if(m%2==1)tmp=(tmp*x)%mod;
27     return tmp;
28 }
29 int main()
30 {
31     scanf("%lld %lld",&n,&k);
32     inv[0]=inv[1]=1;jc1[0]=1;jc2[0]=1;tpower[0]=1;
33         for(LL i=2;i<=n;i++) 
34             inv[i]=((p-p/i)*inv[p%i])%p;
35         for(LL i=1;i<=n;i++) 
36             jc1[i]=(jc1[i-1]*i)%p,
37             jc2[i]=(jc2[i-1]*inv[i])%p,
38             tpower[i]=(tpower[i-1]*2)%(p-1);
39     LL zt=1; 
40     for(LL i=k;i<=n;i++,zt=-zt)
41         ans+=((C(n,i)*(1ll*qpow(2,tpower[n-i],p)-1))%p*C(i,k)*1ll)%p*zt*1ll;
42     printf("%lld
",1ll*((ans+p)%p+p)%p);
43 }

View Code