题目链接

题解

考虑交集至少为 $i$ 个的情况，设方案数为 $g [i]$ ，显然

g[i]=\binom{n}{i}(2^{2^{n-i}}-1)

容斥一下，答案就是

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

代码

#include 
    
     int read(){
      int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
          if(ch=='-')        {
              f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
          x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=1000000;const int mod=1000000007;int n,k,fac[maxn+10],ifac[maxn+10],ans;int quickpow(int a,int b,int m){
      int res=1;  while(b)    {
          if(b&1)        {
              res=1ll*res*a%m;        }      a=1ll*a*a%m;      b>>=1;    }  return res;}int C(int a,int b){
      return 1ll*fac[a]*ifac[b]%mod*ifac[a-b]%mod;}int main(){
      n=read();  k=read();  fac[0]=1;  for(int i=1; i<=n; ++i)    {
          fac[i]=1ll*fac[i-1]*i%mod;    }  ifac[n]=quickpow(fac[n],mod-2,mod);  for(int i=n-1; i>=0; --i)    {
          ifac[i]=1ll*ifac[i+1]*(i+1)%mod;    }  int op=1;  for(int i=k; i<=n; ++i)    {
          ans=(ans+1ll*op*C(n-k,n-i)%mod*(quickpow(2,quickpow(2,n-i,mod-1),mod)-1+mod))%mod;      op=mod-op;    }  printf("%lld\n",1ll*ans*C(n,k)%mod);  return 0;}