menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[容斥+二项式反演]BZOJ2839【集合计数】题解
local_offer 查看标签
comment 0 条评论

题目概述

有一个 $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{align} 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{align} $$

(那个组合数的公式可以这么理解:从 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up