Description：

$n$ 个元素的集合，选出若干子集使得交集大小为 $k$ ，求方案数。

$1\le n,k \le 1000000$

Solution：

设 $S[i]$ 表示交集大小至少为 $i$ 的方案数，根据容斥原理， $\begin{align}ans=\sum_{i=k}^n(-1)^{i-k}S[i]\end{align}$

枚举一定选的是哪些元素，有 $C_n^i$ 种方案，包含这些元素的集合有 $2^{n-i}$ 个，这些集合都可以选或不选，但不能都不选，方案数为 $2^{2^{n-i}}-1$ ，每个集合都会产生 $C_i^k$ 的方案数，所以 $S[i]=C_i^k\times C_n^i\times(2^{2^{n-i}}-1)$ ，答案就是 $\begin{align}\sum_{i=k}^n(-1)^{i-k}C_i^kC_n^i(2^{2^{n-i}}-1)\end{align}$ 。组合数可以预处理阶乘和阶乘的逆元 $O(1)$ 查询，关于 $2^{2^{n-i}}$ 怎么求，可以 $O(n)$ 预处理 $n$ 以内二的幂次，然后用快速幂暴力算，更好的做法是 $2^{2^{i}}=2^{2^{i-1}\times2}=(2^{2^{i-1}})^2$ 这样做的话这题复杂度就是 $O(n)$ 的了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 1000010

typedef long long ll;

ll pow2[MAXN];

#define MOD 1000000007

#define PHI 1000000006

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

ll fac[MAXN],inv[MAXN];

ll C(int n,int m){return fac[n] * inv[m] % MOD * inv[n - m] % MOD;}

int main()

{

	scanf("%d%d",&n,&k);

	pow2[0] = 1;

	for(int i = 1;i <= n;++i)pow2[i] = (pow2[i - 1] * 2) % PHI;

	fac[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = fac[i - 1] * i % MOD;

	inv[n] = power(fac[n],MOD - 2);

	for(int i = n - 1;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % MOD;

	ll ans = 0;

	for(int i = k;i <= n;++i)

	{

		ll res = C(n,i) * C(i,k) % MOD * (power(2,pow2[n - i]) - 1 + MOD) % MOD;

		ans = (ans + res * ((i - k) % 2 == 0 ? 1 : -1) + MOD) % MOD;

	}

	cout << ans << endl;

	return 0;

}