BZOJ 2839: 集合计数解题报告

BZOJ 2839: 集合计数

Description

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

它们的交集的元素个数为(K)，求取法的方案数，答案模(1000000007)。

Input

一行两个整数(N,K)

Output

一行为答案。

HINK

对于(100\%)的数据，(1≤N≤1000000,0≤K≤N)；

设交集拥有元素集合(S)的取法方案数为(f(S))，有

[f(S)=2^{2^{n-|S|}}-1 ]

则答案为

[sum_{|T|=k} sum_{i=k}^n(-1)^{i-k}sum_{Ssupseteq T,|S|=k}f(S) ]

代入得

[inom{n}{k}sum_{i=k}^n(-1)^{i-k}inom{n-k}{i-k}(2^{2^{n-i}}-1) ]

直接预处理一下就可以算了

Code:

#include <cstdio>
const int N=1e6+10;
const int mod=1e9+7;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
#define mul(a,b) (1ll*(a)*(b)%mod)
int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}
int inv[N],fac[N],po[N];
int C(int m,int n){return mul(fac[m],mul(inv[m-n],inv[n]));}
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	fac[0]=1;for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
	inv[n]=qp(fac[n],mod-2);
	for(int i=n-1;~i;i--) inv[i]=mul(inv[i+1],i+1);
	po[0]=2;for(int i=1;i<=n;i++) po[i]=mul(po[i-1],po[i-1]);
	int ans=0,cur=1;
	for(int i=k;i<=n;i++)
	{
		int yuu=mul(C(n-k,i-k),add(po[n-i],mod-1));
		ans=add(ans,cur?yuu:mod-yuu);
		cur^=1;
	}
	ans=mul(ans,C(n,k));
	printf("%d
",ans);
	return 0;
}