引入

關于子集個數

關于 \(n\) 個元素的集合 \(U\) 的子集個數，有兩種理解方式。

• 組合數理解
  從\(n\) 個元素的集合中能夠選擇構造出 \(\binom{n}{0}\) 個空集， $\binom{n}{1} $ 個元素個數為 $ 1$ 的集合，以此類推，子集個數即為
  \[\left | \left \{ S | S \in U \right \} \right | =\sum_{i=0}^{n} \binom{n}{i} = 2^n \]

• 01狀態理解
  有 \(n\) 個位置，每個位置上的元素對應集合 \(U\) 的對應元素，每個位置有選或不選兩個決策，即
  \[\left | \left \{ S | S \in U \right \} \right | =2^n \]

關于二項式反演的其中一個形式

對于集合 \(U\) 和 \(n\) 個屬性 \(S_i\)，令 \(f(x)\) 表示至少「欽定」\(x\) 個屬性的方案數，「欽定」的意義即

令 \(g(x)\) 為恰好涉及 \(x\) 個屬性的方案數，則有如下

題解

設集合 \(S\) 表示集合 \(U\) 的 \(2^n\) 個子集構成的集合，\(\left | S \right |=2^n\)，題目讓求的是有多少個方案滿足 \(S\) 的子集 \(T\) 使得 \(\left | \bigcap_{T \subseteq S} T \right |=k\) ，考慮二項式反演，令 \(f(x)\) 表示「欽定」交集的大小為 \(x\) 的集合的方案數，則有

解釋一下，滿足大小為 \(x\) 的情況有 \(\binom{n}{x}\) 個元素，剩余可以選 \(2^{n-x}\) 個集合，其子集有 \(2^{2^{n-x}}\) 個集合，但有一個是空集，減去一個 \(1\) 即可。令 \(g(x)\) 表示交際大小恰好為 \(x\) 的方案數，則有

將 \(f(x)\) 代入原式，\(g(k)\) 即為最終答案

在計算 \(2^{2^{n-i}} \mod P\) 時，需要用到擴展歐拉定理，即 \(2^{2^{n-i}} \equiv 2^{2^{n-i} \mod (P-1)} \pmod{P}\)

CODE

#include<cstdio>
using namespace std;

const int N=1e6+5;
const int P=1e9+7;
typedef long long ll;
ll fc[N];
ll infc[N];
ll n,k,ans;

ll binpow(ll a,ll b,ll mod){
    ll res=1;
    while (b){
        if (b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res%mod;
}

void fact_init(){
    fc[0]=1;
    for (int i=1;i<=n;i++) fc[i]=(fc[i-1]*i)%P;
    for (int i=0;i<=n;i++) infc[i]=binpow(fc[i],P-2,P)%P;
}

ll C(ll n,ll m){
    return fc[n]%P*infc[m]%P*infc[n-m]%P;
}

int main(){
    scanf("%lld%lld",&n,&k);
    fact_init();
    for (int i=k;i<=n;i++){
        ll t=(((C(n,i)*C(i,k))%P)*(binpow(2,binpow(2,n-i,P-1),P)-1)%P)%P;
        if ((i-k)%2==1) t*=-1;
        ans=((ans+t)%P+P)%P;
    }
    printf("%lld\n",ans);
    return 0;
}