传送门
题意简述:对于一个有N个元素的集合在其2^N个子集中取出若干集合(至少一个),使得它们的交集的元素个数为K,求取法的方案数。
思路:考虑枚举相交的是哪kkk个,有CnkC_n^kCnk种方案,然后考虑剩下的可选可不选一共有22n−k2^{2^{n-k}}22n−k种选法,但是这样选出来的集合可能有其余的数相交,因此我们容斥掉多余的:
ans=Cnk∗∑i=0n−kCni22n−k−ians=C_n^k*\sum_{i=0}^{n-k}C_n^i2^{2^{n-k-i}}ans=Cnk∗∑i=0n−kCni22n−k−i
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
const int N=1e6+5,mod=1e9+7,mod1=1e9+6;
int ans=0,fac[N],ifac[N],n,k;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline int mul1(const int&a,const int&b){return (ll)a*b%mod1;}
inline int C(int n,int m){return mul(mul(fac[n],ifac[m]),ifac[n-m]);}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
inline int ksm1(int a,int p){int ret=1;for(;p;p>>=1,a=mul1(a,a))if(p&1)ret=mul1(ret,a);return ret;}
inline void init(){
fac[0]=ifac[0]=fac[1]=ifac[1]=1;
for(ri i=2;i<=n;++i)fac[i]=mul(fac[i-1],i),ifac[i]=mul(ifac[mod-mod/i*i],mod-mod/i);
for(ri i=2;i<=n;++i)ifac[i]=mul(ifac[i],ifac[i-1]);
}
int main(){
freopen("lx.in","r",stdin);
cin>>n>>k,init();
for(ri tmp,i=0;i<=n-k;++i){
tmp=mul(C(n-k,i),ksm(2,ksm1(2,n-k-i)));
i&1?ans=dec(ans,tmp):ans=add(ans,tmp);
}
cout<<mul(C(n,k),ans);
return 0;
}