题目描述
一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得
它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）
题解
假设我们已经确定了这k个元素都是谁，最后再乘上C(n,k)就可以了。
根据容斥原理(二项式反演)可知，答案为选出至少k个的方案数-选出至少k+1个的方案数+选出至少k+2个的方案数。。。
如何求选出至少x个的方案数，考虑有多少种集合包含x个元素，答案是2n-x(相当于我们已经确定了x个元素)。
他们中每个集合都可以选或不选，但是不能都不选。
所以是2r-1,r是刚才那个2n-x。
最后因为我们固定了k个，有x-k个没有固定，再乘上C(n-k,x-k)。
注意指数要%mod-1。
代码
#include<iostream>
#include<cstdio>
#define N 1000009
using namespace std;
typedef long long ll;
const int mod=1e9+;
ll inv[N],jie[N],ni[N],n,k,ans;
inline ll power(ll x,ll y){
ll ans=;
while(y){
if(y&)ans=ans*x%mod;x=x*x%mod;y>>=;
}
return ans;
}
inline ll C(int n,int m){
return jie[n]*ni[m]%mod*ni[n-m]%mod;
}
int main(){
cin>>n>>k;
inv[]=;
for(int i=;i<=n;++i)inv[i]=inv[i-]*%(mod-);
jie[]=;
for(int i=;i<=n;++i)jie[i]=jie[i-]*i%mod;ni[n]=power(jie[n],mod-);
for(int i=n-;i>=;--i)ni[i]=ni[i+]*(i+)%mod;
for(int i=k;i<=n;++i){
if((i-k)&)ans-=C(n-k,i-k)*(power(,inv[n-i])-)%mod;
else ans+=C(n-k,i-k)*(power(,inv[n-i])-)%mod;
ans=(ans%mod+mod)%mod;
}
ans=ans*C(n,k)%mod;
cout<<ans;
return ;
}