题目描述

一个有$N$个元素的集合有$2^N$个不同子集（包含空集），现在要在这$2^N$个集合中取出若干集合（至少一个），使得
它们的交集的元素个数为$K$，求取法的方案数，答案模$1e9+7$。

输入格式

一行两个整数$N,K$

输出格式

一行为答案。

对于$100$%的数据，$1≤N≤1000000$；$0≤K≤N$；

$ (TimeLimit:1s,MemoryLimit:128M)$

思路

我们首先确定我们交集所包含的$k$个元素，一共有$\binom{n}{k}$种方法。

假定我们当前确定的包含$k$个的元素的集合为$S$。

那么包含$S$的子集相当于在除了$S$包括的元素中，选任意多元素的元素凑成的子集。

那么包含$S$的所有子集有
$$ \sum_{i=0}^{n-k}\binom{n-k}{i}=2^{n-k} $$
个

从中选任意多个集合相交共有
$$ \sum_{i=1}^{2^{n-k}}\binom{2^{n-k}}{i}=\sum_{i=0}^{2^{n-k}}\binom{2^{n-k}}{i}-\binom{2^{n-k}}{0}=2^{2^{n-k}}-1 $$
种方案

但是这样算是所有交集大于等于$k$个元素的方案，即除了$S$还有其他的交集。

那么我们就要把其中所有交集大小大于$k$个元素的方案给减掉。

所有交集大小大于$k$个元素的方案等价于所有交集大小大于等于$k+1$个元素的方案。

我们当前的方案已经确定了包含$k$个元素的集合$S$，那么我们只需要在除了$S$的元素中任选一个即可凑成一个包含$k+1$个元素的集合，设除了$S$以外的元素为$a$,那么我们就可以用上面的方法算出交集至少为$S,a$的方案数。其中$a$共有$\binom{n-k}{1}$种选法。

那么是否我们直接减去
$$ \binom{n-k}{1}(2^{2^{n-k-1}}-1) $$

就是交集恰好为$S$的方案数呢？

考虑下面的情况：

{$Sabcd,Sabcf$}

交集为$Sabc$

而当我们确定交集至少为$Sa,Sb,Sc$都可以凑成这种方案，也就会产生重复计数导致答案变小。

我们设$P_a$为交集除了包括$S$，还需包括$a$的集合。

那么我们要求的是一个并集的关系，即
$$ \left|\bigcup P \right| $$
我们考虑任意两个方案集合$P_a$与$P_b$的交集
$$ \left|P_a \bigcap P_b \right| $$
考虑其意义，即满足交集至少包含$S$，$a$，$b$的方案。

那么有

$$ \left|P_a \bigcap P_b \right|=(2^{2^{n-k-2}}-1) $$

其方案集合交集的大小只与相交集合的个数有关，与具体是哪几个相交无关。

而$P$集合一共有$n-k$个

那么有
$$ \left|\bigcup P \right|=\sum_{i=1}^{n-k}\binom{n-k}{i}(-1)^{i-1}(2^{2^{n-k-i}}-1) $$

那么确定交集为$k$个元素的方案数为
$$ \begin{aligned} (2^{2^{n-k}}-1)-\left|\bigcup P \right|&=(2^{2^{n-k}}-1)-\sum_{i=1}^{n-k}\binom{n-k}{i}(-1)^{j-1}(2^{2^{n-k-i}}-1)\\\ &=(2^{2^{n-k}}-1)+\sum_{i=1}^{n-k}\binom{n-k}{i}(-1)^{i}(2^{2^{n-k-i}}-1)\\\ &=\sum_{i=0}^{n-k}\binom{n-k}{i}(-1)^{i}(2^{2^{n-k-i}}-1) \end{aligned} $$
那么答案为
$$ \binom{n}{k}\times \sum_{i=0}^{n-k}\binom{n-k}{i}(-1)^{i}(2^{2^{n-k-i}}-1) $$
那么不同的两个交集$S$和$A$之间的方案是否会有冲突？

那么显然是不会的，在我们上面的计算中，可以确保我们每种选$k$个元素的方案的交集一定是交集恰好为$S$或$A$的。

代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10,mod = 1e9 + 7;

long long fac[N],invfac[N],two[N];

int C(int n,int m){return n<m?0:(long long)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}

inline void init(){
    fac[0]=invfac[0]=invfac[1]=1;
    for(int i=1;i<=N - 10;i++)fac[i]=(long long)fac[i-1]*i%mod;
    for(int i=2;i<=N - 10;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
    for(int i=2;i<=N - 10;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
    two[0] = 2;
    for (int i = 1; i <= N - 10; i++){
        two[i] = two[i - 1] * two[i - 1] % mod;
    }
}

int main(){
    init();
    int n,k;
    cin >> n >> k;
    long long ans = 0;
    for (int i = 0;i <= n - k; i++){
        if ((i % 2) == 0) ans = (ans + C(n-k,i) * (two[n - k - i] - 1) % mod) % mod;
        else ans = (ans - C(n-k,i) * (two[n - k - i] - 1) % mod + mod) % mod; 
    }
    cout << C(n,k) * ans % mod;
    return 0;
}