2839: 集合计数

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

---

先选出k个\(\binom{n}{k}\)，剩下选出一些集合交集为空集

考虑容斥

\[ 交集为\emptyset = 任意选的方案数-交集\ge 1 的方案数+交集\ge 2的方案数-... \]

交集\(\ge i\)就是说先选出i个元素在交集里，剩下的元素的集合任选

那么就是

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

组合数直接推阶乘和逆元

后面的\(2^{2^x}\)，考虑快速幂的过程\(2^{2^i}=2^{2^{i-1}}2^{2^{i-1}}\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=1e6+5, P=1e9+7;typedef long long ll;inline int read(){    char c=getchar(); int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n, k;ll ans, now=2, inv[N], fac[N], facInv[N];inline ll C(int n, int m) {return fac[n]*facInv[m]%P*facInv[n-m]%P;}inline void mod(ll &x) {if(x>=P) x-=P;}int main() {    freopen("in","r",stdin);    n=read(); k=read();    inv[1]=1; fac[0]=facInv[0]=1;    for(int i=1; i<=n; i++) {        if(i!=1) inv[i] = (P-P/i)*inv[P%i]%P;        fac[i] = fac[i-1]*i%P;        facInv[i] = facInv[i-1]*inv[i]%P;    }    n -= k;    for(int i=n; i>=0; i--) {        (ans += ((i&1) ? -1 : 1) * C(n, i)*(now-1)%P) %=P;        now = now*now%P;    }    if(ans