数学、组合数学、二项式反演

首先钦定 $k$ 个元素被选择，任意地选取至少一个包含这 $k$ 个元素的子集的选取方法的数量为

$$g(k) = C(n,k) (2^{2^{n-k}} - 1)$$

注意不同选取方法可能生成相同被选集合，使用 $f(k)$ 表示交集恰好有 $k$ 个元素的选择方案，则

$$g(k) = \sum_{i=k}^{n} C(i,k) f(i)$$

考虑这个式子，由于除了被钦定的 $k$ 个元素以外的元素都是任意选择的，$f(i)$ 对应的每个选择结果会被 $C(i,k)$ 个选取方法统计到。二项式反演。

$$f(k) = \sum_{i=k}^{n} (-1)^{i-k} C(i,k) g(i)$$

注意幂次上应该对 $10^9+6$ 取模，而不是直接对 $10^9+7$ 取模。

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1'000'000'007;
Combination<Mint<mod>,1'000'005,mod> C;
Mint<mod> ans;
int n,k;
inline Mint<mod> g(int x){return C(n,x)*(Mint<mod>(2).multiply(Mint<mod-1>(2).multiply(n-x).x)-1);}
int main(){
    cin>>n>>k;
    for(int i=k;i<=n;i++) ans+=Mint<mod>(-1).multiply(i-k)*C(i,k)*g(i);
    cout<<ans<<'\n';
    return 0;
}