**# Description

link

给一个 \(n\) 元集，从中取若干个子集求交，求交集大小为 \(k\) 的方案数

\(n,k\le 10^6\)

Solution

设 \(f_i\) 为交集大小至少为 \(i\) 的方案数

然后上容斥：

\[ans=\sum^{n}_ {i=k} (-1)^{i-k} f_i \]

对于这个题，先钦定交集中的 \(k\) 个元素

最后乘上 \(\binom n k\) 就好了

对于每个 \(i\) 考虑

这里剩下了 \(n-i\) 个元素

我们把它们建一个集合，集合中非空子集元素共 \(2^{n-i}-1\) 个

表示取完 \(i\) 个之后还要取哪些元素

我们发现因为是取若干个，所以方案可以表示为

\[2^{2^{n-i}} \]

我们上来先定了 \(k\) 个，所以只用乘上 \(\binom{n-k}{i-k}\) 即可

最后写成式子

\[ans=\binom{n}{k}\sum_{i=k}^{n} (-1)^{i-k} \binom{n-k}{i-k} 2^{2^{n-i}} \]

预处理组合数和平方

这里注意！！！！平方取模的时候要取 \(mod-1\)

原因：指数上欧拉定理

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res*f;
	}
	const int N=1e6+10,mod=1e9+7;
	int fac[N],inv[N],n,p[N],k;
	inline void prework()
	{
		fac[1]=fac[0]=1; inv[0]=inv[1]=1; p[0]=1;
		for(int i=1;i<N;++i) fac[i]=fac[i-1]*i%mod;
		for(int i=2;i<N;++i) inv[i]=mod-mod/i*inv[mod%i]%mod;
		for(int i=1;i<N;++i) inv[i]*=inv[i-1],inv[i]%=mod;
		for(int i=1;i<N;++i) p[i]=p[i-1]*2%(mod-1);
		return ;
	}
	inline int ksm(int x,int y)
	{
		int res=1; for(;y;y>>=1,(x*=x)%=mod) if(y&1) (res*=x)%=mod;
		return res;
	}
	inline int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
	signed main()
	{
		n=read(); k=read(); prework();
		int ans=0;
		for(int i=k;i<=n;++i)
		{
			if((i-k)&1) ans-=C(n-k,i-k)*((ksm(2,p[n-i])-1+mod)%mod)%mod;
			else ans+=C(n-k,i-k)*(ksm(2,p[n-i])-1)%mod;
			ans+=mod,ans%=mod;
		}
		ans*=C(n,k); ans%=mod; 
		printf("%lld\n",ans); 
		return 0;
	}
}
signed main(){return yspm::main();}
```**