BZOJ 2839: 集合计数 解题报告

时间：2021-02-24 08:31:29

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_{S\supseteq T,|S|=k}f(S)
\]

代入得

\[\binom{n}{k}\sum_{i=k}^n(-1)^{i-k}\binom{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\n",ans);

	return 0;

}

2019.2.28

相关文章