首先从 $n$ 个元素中选出 $m$ 个作为交集，方案数是 $C(n,m)$，然后还剩下 $n-m$ 个元素，假设可以构成 $2^{n-m}$ 种集合，然后从这么些集合中再选，就是 $2^{2^{n-m}}$ 种方案。然后发现这样算会重，因为它的组合意义是交集至少为 $m$，所以使用容斥。

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n,m;
int fac[1000005],inv[1000005];
int Pow(int a,int b,int p){
	int as=1,bs=a;
	while(b){
		if(b&1)as=as*bs%p;
		bs=bs*bs%p;
		b>>=1;
	}
	return as;
}
int C(int n,int m){
	if(m<0||n<m)return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
	cin>>n>>m;
	fac[0]=inv[0]=1;for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mod,inv[i]=Pow(fac[i],mod-2,mod);
	int ans=0;
	for(int i=0;i<=n-m;++i){
		if((n-m-i)&1)ans=(ans-C(n-m,i)*Pow(2,Pow(2,i,mod-1),mod)%mod+mod)%mod;
		else ans=(ans+C(n-m,i)*Pow(2,Pow(2,i,mod-1),mod)%mod)%mod;//你还要从n-m个里面选出i个作为构成集合的
	}
	cout<<ans*C(n,m)%mod;
	return 0;
}

这个题还有另一个思路

二项式反演

$g(n)=\sum^{N}_{i=n}C(i,n)f(i)$

他就等价于

$f(n)=\sum^{N}_{i=n}(-1)^{i-n}C(n,i)g(i)$

我们认为g(n)为至少有n种元素，f(n)为有且仅有n种元素

然后$g(n)=C(n,i)(2^{2^{n-i}}-1)$

然后就做完了

#include <bits/stdc++.h>
using namespace std;

const long long p = 1e9 + 7;

const long long N = 1e6 + 10;

long long fac[N], inv[N], power[N];

long long n, m;

void init(){
	fac[0] = inv[0] = inv[1] = 1;
	for(long long i = 1;i < N; i++){
		fac[i] = fac[i-1] * i % p;
	}
	for(long long i = 2;i < N; i++){
		inv[i] = (p - p / i) * inv[p % i] % p;
	}
	for(long long i = 1;i < N; i++){
		inv[i] = inv[i] * inv[i-1] % p;
	}
	power[0] = 2;
	for(int i = 1;i <= n; i++) power[i] = power[i-1] * power[i-1] % p;
}

long long C(long long n,long long m){
	if(n < m) return 0;
	if(n < p && m < p) return fac[n] * inv[m] % p * inv[n-m] % p;
	return C(n/p,m/p) * C(n%p,m%p) % p;
}

int main(){
	cin >> n >> m;
	init(); 
	long long ans = 0;
	for(long long i = m;i <= n; i++){
		if((i-m)%2==1) ans = (ans - C(i,m) * C(n,i) % p * (power[n-i] - 1 + p) % p + p) % p;
		else ans = (ans + C(i,m) * C(n,i) % p * (power[n-i] - 1 + p) % p) % p;
	}
	cout << ans;
	return 0;
}