有一个 $n$ 个元素的集合,求选出若干个子集(不可以不选)相交后元素个数刚好为 $K$ 的方案数。
学Min-Max容斥的时候没有考虑过怎么构造,导致这道题的构造方法理解了半天……
先讲一波二项式反演,学习自Miskcoo:
$$ 1.f_n = \sum_{i=0}^n (-1)^i {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^i {n \choose i} f_i\\ 2.f_n = \sum_{i=0}^n {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^{n-i} {n \choose i} f_i $$
证明的话考虑代入以及熟悉的换循环顺序操作:
$$ \begin{aligned} 1.g_n&=\sum_{i=0}^{n}(-1)^i{n\choose i}f_i=\sum_{i=0}^{n}(-1)^i{n\choose i}\sum_{j=0}^{i}(-1)^j{i\choose j}g_j\\ ∵&{n\choose i}{i\choose j}={n\choose j}{n-j\choose i-j}\\ ∴g_n&=\sum_{i=0}^{n}(-1)^{i}\sum_{j=0}^{i}(-1)^{j}{n\choose j}{n-j\choose i-j}g_j\\ &=\sum_{j=0}^{n}(-1)^{j}{n\choose j}g_j\sum_{i=j}^{n}(-1)^{i}{n-j\choose i-j}\\ &=\sum_{j=0}^{n}(-1)^{j}{n\choose j}g_j\sum_{i=0}^{n-j}(-1)^{i+j}{n-j\choose i}\\ &=\sum_{j=0}^{n}(-1)^{2j}{n\choose j}g_j\cdot(1-1)^{n-j}=\sum_{j=0}^{n}{n\choose j}g_j\cdot0^{n-j} \end{aligned} $$
(那个组合数的公式可以这么理解:从 $n$ 个元素中选出 $i$ 个,然后再从 $i$ 个元素中选出 $j$ 个特殊元素,那么等价于先从 $n$ 个里选出 $j$ 个特殊元素,然后再从剩下的 $n-j$ 个里面选出 $i-j$ 个元素,当然暴力展开也可以证明啊)
最后那个式子只在 $j=n$ 的时候不为 $0$ ,也就是 $g_n$ ,得证。那么第二个反演式子的证明同理(第二个也更常见)。
刚好为 $K$ 根本不可做,考虑求出至少为 $K$ 个然后容斥就行啦。
令 $a(i)$ 表示至少 $i$ 个的方案数,我刚开始斯波地认为容斥式子长这样,甚至让我怀疑我容斥学假了……
$$ a(i)={n\choose i}(2^{2^{n-i}}-1),ans=\sum_{i=K}^{n}(-1)^{i-K}a(i) $$
这显然是不对的……实际上应该要想办法构造出这个容斥系数 $f(i)$ ,令答案为:
$$ ans=\sum_{i=0}^{n}f(i)a(i) $$
考虑集合 $S$ 的贡献:
$$ b_S\sum_{T\subseteq S}f(|T|) $$
$b_S$ 表示交出 $S$ 的方案数,由于对于所有 $S$ 的子集 $T$ ,$a(|T|)$ 都会出现 $b_S$ 次交为 $S$ 的方案,只需要考虑容斥系数。又因为显然 $b_S$ 和 $f(|T|)$ 都只和集合大小有关,所以可以改成交出大小为 $x$ 的方案数:
$$ b_x\sum_{i=0}^{x}f(i){x\choose i} $$
那么总方案数为 $\sum_{i=0}^{n}b_i\sum_{j=0}^{i}f(j){i\choose j}$ ,由于 $ans=b_K$ ,所以需要满足 $\sum_{j=0}^{i}f(j){i\choose j}=[i=K]$ 。
后面那个其实也是个函数,根据二项式反演:
$$ f(x)=\sum_{i=0}^{x}(-1)^{x-i}{x\choose i}[i=K]=(-1)^{x-K}{x\choose K} $$
所以得到:
$$ ans=\sum_{i=K}^{n}(-1)^{i-K}{i\choose K}{n\choose i}(2^{2^{n-i}}-1) $$
这个式子好像也被叫做广义容斥定理来着?
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000000,MOD=1e9+7;
int n,K,fac[maxn+5],INV[maxn+5],pw[maxn+5],ans;
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(int n){
INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
pw[0]=2;for (int i=1;i<=n;i++) pw[i]=(LL)pw[i-1]*pw[i-1]%MOD;for (int i=0;i<=n;i++) AMOD(pw[i],MOD-1);
}
#define C(x,y) ((x)<(y)?0:((LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD))
int main(){
freopen("program.in","r",stdin);freopen("program.out","w",stdout);
scanf("%d%d",&n,&K);Make(n);
for (int i=K;i<=n;i++) {int now=i-K&1?MOD-1:1;now=(LL)now*C(i,K)%MOD*C(n,i)%MOD*pw[n-i]%MOD;AMOD(ans,now);}
return printf("%d\n",ans),0;
}