因为要在n个里面选k个，所以我们先枚举选的是哪$k$个，方案数为$C_{n}^k$
确定选哪k个之后就需要算出集合交集正为好这$k$个的方案数，考虑用容斥原理。
我们还剩下$n-k$个元素，交集至少为$k$的方案数为$2^{2^{n-k}}$。
相当于在仅有剩下$n-k$个元素的集合里随便选，最后再往每个集合里塞进这$k$个元素。
然后就是很简单的容斥了。
减去交集至少为k加上其他一个元素的方案数，加上交集至少为k加上其他两个元素的方案数。。。
$$ans=C_{n}^k\times(2^{2^{n-k}}-C_{n-k}^1\times 2^{2^{n-k-1}}+C_{n-k}^2\times 2^{2^{n-k-2}}-.....)$$
好像网上其他做法跟我不太一样呢。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000005
#define ll long long
using namespace std;
const int p = ;
int n,k;
ll pw(int x,int y)
{
ll lst=;
while(y)
{
if(y&)lst=lst*x%p;
y>>=;
x=(ll)x*x%p;
}
return lst;
}
int pow[N],jie[N];
int main()
{
pow[]=;jie[]=;
scanf("%d%d",&n,&k);
for(int i=;i<=n-k;i++)pow[i]=(pow[i-]*)%(p-);
for(int i=;i<=n;i++)jie[i]=(1LL*jie[i-]*i)%p;
ll ans=;
ans=pw(,pow[n-k]);
for(int i=;i<=n-k;i++)
{
int tmp=1LL*pw(,pow[n-k-i])*jie[n-k]%p*pw(jie[i],p-)%p*pw(jie[n-k-i],p-)%p;
if(i&)ans=(ans-tmp+p)%p;
else ans=(ans+tmp)%p;
}
ans=ans*jie[n]%p*pw(jie[k],p-)%p*pw(jie[n-k],p-)%p;
printf("%lld\n",ans);
return ;
}