题目

这篇题解的背景。。。（可以跳过，与题目无关）

说实话，有点恼，也 觉得自己有点唐，在以为自己已经理解了变量意义的情况下（实际上并没有）去推了半天错式子，甚至

我推出了他不对时还给自己否定了，昨天晚三还拉着\(9G\) 与我一块推。。。，结果上午发觉好像意义理解错了。。。抽象，

就当是一种历练了

分析

（以下所有知识点与变量与 \(oi-wiki\) 上几乎相同，各位可以去理解一下原理论）

题目让我们去选大集合里的子集组成的新集合，要求新集合的交集个数大于等于 \(k\) 个，

思路还是比较清晰的，由于一个元素个数为 \(k\) 的子集也符合答案，所以我们可以先把元素个数为 \(k\) 个的子集先取出来，

有 \(C^{k}_{n}\) 种，剩下的 \(n-k\) 个数组成的集合有 \(2^{n-k}\) 个，我们从这些集合里选子集组成我们答案，有\(2^{2^{n-k}}\) 种，因为不能

一个也不选，所以要减一，对此我们的总方案数 \(g_{i}=C^{i}_{n}*(2^{2^{n-i}}-1)\) 。

这里的选取肯定是有重复的（ 类似于 {A}{ABC} 与 {ABC} 之类的 ）,这里可以用容斥原理推式子，但有更简洁的方法

——二项式反演,或者可以看一下大佬的博客,反正肯定能看懂，看不懂就多看几个下午，不会有人看不懂吧，那么如何

将公式运用到题目中呢，我们现在已经知道， \(f_n\) 表示恰好使用 \(n\) 个不同元素形成特定结构的方案数，\(g_n\) 表示从 \(n\) 个

不同元素中选出 \(i \geq 0\) 个元素形成特定结构的总方案数。而我们之前已经求得这里 \(g_n\) 的个数了，而求的答案实际上就

是\(f_k\),这样完美符合二项式反演的公式条件，直接带入公式$$f_k=\sum^{n}_{i=k} (-1)^{i-k} C^{k} _{i} g_i$$

可得答案为$$f_k=\sum^{n}_{i=k} (-1)^{i-k} C^{k} _{i} C^{i} _{n} * ( 2 ^ {2 ^ {n-i}}-1)$$

solution

#include<bits/stdc++.h>
#define int long long 
const int maxn=1e7+10;
using namespace std;
int n,k,flag,jc[maxn],ny[maxn],jcny[maxn],ans;
int r=1000000007;

void pre()
{
	jc[0]=jc[1]=ny[0]=ny[1]=jcny[0]=jcny[1]=1;
	for(int i=2;i<=n;i++)
	{
		ny[i]=(r-(r/i)*ny[r%i])%r;
		jcny[i]=jcny[i-1]*ny[i]%r;
		jc[i]=jc[i-1]*i%r;
	}
}

int f(int n,int m)
{
	return jc[n]*jcny[m]%r*jcny[n-m]%r;
}

signed main()
{
	scanf("%lld%lld",&n,&k);
	pre(); 
	for(int i=n,flag=((n-k)&1)?-1:1,temp=1;i>=k;i--)
	{
		ans=(ans+flag*f(i,k)*f(n,i)%r*temp%r+r)%r;
		flag=-flag;
		temp=temp*(temp+2)%r;
	}
	printf("%lld",ans); 
	
	return 0;
}