BZOJ 2839 集合计数

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；

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

组合数问题+容斥原理~

我们先取出k个数，c(n,k)。

然后，n-=k，我们就需要把剩下的取出不相交的几组。

枚举有哪些一定会选，sum(i=0~n){(-1)^i*c(n,i)*(2^(2^(n-i)-1))}。

其中一定有这i个数的组合一共有2^(n-i)种，即枚举剩下的选不选，然后，又要枚举这些集合有哪些是要留下的，但是不能一个都没有，就是答案了。

又被mod卡WA，所有东西都要取模！所以说如果不卡空间还是开long long比较好啊！

#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define ll long long #define mod 1000000007 int n,k,sheng[1000001],jiang[1000001],ans; int mi(int u,int v) { int w=1;u%=mod; for(;v;v>>=1,u=(ll)u*u%mod) if(v&1) w=(ll)w*u%mod; return w; } int c(int u,int v) { return (ll)sheng[u]*jiang[v]%mod*jiang[u-v]%mod; } int solve(int n) { int ans=0,f,k=1; for(int i=n;~i;i--) { if(i&1) ans-=(ll)c(n,i)*k%mod; else ans+=(ll)c(n,i)*k%mod; ans%=mod;f=(ll)k*k%mod;f=(f+k*2%mod)%mod;k=f; } return ans; } int main() { scanf("%d%d",&n,&k);sheng[1]=1; for(int i=2;i<=n;i++) sheng[i]=(ll)sheng[i-1]*i%mod; jiang[n]=mi(sheng[n],mod-2); for(int i=n-1;~i;i--) jiang[i]=(ll)jiang[i+1]*(i+1)%mod; ans=(ll)solve(n-k)*c(n,k)%mod; ans=(ans+mod)%mod; printf("%d\n",ans); return 0; }