传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=2839
Sol
二项式反演
设$g_i$表示随机选若干个集合 交集至少为$i$个的方案
$g_i$=$C(n,i)$*($2^{2^{n-i}}$$-1$)
用$f_i$表示恰好i个的方案
则有$g_i$=Σ$C(i,j)*f_j$ $ j∈[1,n] $
然后就直接二项式反演
$f_i$=$ΣC(i,j)*g_j*(-1)^{j-i}$
#include <bits/stdc++.h> using namespace std; const long long fish=1e9+7; const int maxn=1e6; long long inv[maxn+5],fac[maxn+5]; long long dp[maxn+5]; long long Pow(long long x,int y){ long long ans=1; for (;y;y>>=1){ if (y%2) ans=ans*x%fish; x=x*x%fish; } return ans; } long long C(int N,int R){ return fac[N]*1ll*inv[R]%fish*inv[N-R]%fish; } int main(){ int N,K; scanf("%d%d",&N,&K); fac[0]=1; for (int i=1;i<=maxn;i++) fac[i]=fac[i-1]*1ll*i%fish; inv[maxn]=Pow(fac[maxn],fish-2); for (int i=maxn-1;i>=0;i--) inv[i]=inv[i+1]*1ll*(i+1)%fish; long long tmp=2; for (int i=N;i>=0;i--){ dp[i]=C(N,i)*(tmp-1)%fish; tmp=tmp*tmp%fish; } long long ans=0; long long tmp1=0; for (int i=K,xs=1;i<=N;i++,xs*=(-1)){ long long tmp1=C(i,K)*dp[i]%fish*xs; if (tmp1<0) (tmp1+=fish)%=fish; ans=(ans+tmp1)%fish; } cout<<ans; }
原文：https://www.cnblogs.com/si--nian/p/11476883.html