二项式反演

二项式反演

基本形式

二项式反演的形式与容斥很类似。

\[f(n)=\sum_{i=0}^{n}(-1)^{i}\binom{n}{i} g(i) \Leftrightarrow g(n)=\sum_{i=0}^{n}(-1)^{i}\binom{n}{i} f(i)\]
有几个更常用的形式

\[\begin{aligned}f(n) =\sum_{i=0}^{n}\binom{n}{i} g(i) &\Leftrightarrow g(n)=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i} f(i) \\ \\f(n) = \sum_{i=m}^n \binom{n}{i} g(i) &\Leftrightarrow g(n) = \sum_{i=m}^n (-1)^{n-i} \binom{n}{i} f(i) \\ \\f(n) = \sum_{i=n}^m \binom{i}{n} g(i) &\Leftrightarrow g(n) = \sum_{i=n}^m (-1)^{i-n} \binom{i}{n} f(i)\end{aligned}\]
只要满足左右任意一个式子就可以转化到另一个式子上去。
其中 \(f(n)\) 表示至多 \(n\) 或者至少 \(n\)（换句话说，钦定 \(n\) 个必须要选/不选，其他元素可以随便选）的方案数，\(g(n)\) 表示恰好选 \(n\) 个，其他的都不能选的方案数。
组合意义

以

\[\begin{aligned}f(n) =\sum_{i=0}^{n}\binom{n}{i} g(i) &\Leftrightarrow g(n)=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i} f(i)\end{aligned}\]
为例。
这里 \(f(n)\) 表示至多选 \(n\) 个的方案数，\(g(n)\) 表示刚好选 \(n\) 个的方案数。
左边的式子的组合意义比较显然，通过枚举选多少个合起来的方案数就是总方案数。
右边的式子就是用类似容斥原理的方式将重复的抵消来得到正确的数量。
注意，这里 \(f(n)\) 是钦定 \(n\) 个要选的数量，其中的情况是会重复的，而且重复的次数很多。因此才会在 \(g(i)\) 前面带一个组合数的系数。
P10596 BZOJ2839 集合计数


\[\text{给定 } n, k \text{，令 } S_0 = \{1, 2, 3, \ldots, n\} \text{，} S_1 = \{ S \mid S \subseteq S_0 \} \text{，求有多少 } S_1 \text{ 的子集 } S \text{ 满足 } \left| \bigcap_{S \in S_1} S \right| = k \text{。}\]
我们设 \(f(x)\) 表示至少有 \(x\) 个数是在交集中的。那么从组合意义方向考虑有

\[f(x)={n\choose x}(2^{2^{n-x}}-1)\]
这里减一是因为前面的二项式系数只是在选定那些数作为交集，而并没有真正地去选定一个集合。后面是统计除了这些数以外的集合的总情况数，然后对于每个集合将前面选定的 \(x\) 个数塞进选定的集合中（因为是取交集，因此每个选定的集合都必须有这 \(x\) 个数）
因此这里减一是为了保证至少有一个集合选了而不是一个集合都不选，这样交集就不可能包含所选定的这 \(x\) 个数。（交集就变成了空集）
发现要求的东西就是恰好有 \(k\) 个数在交集中，我们将其设为 \(g(k)\)。那按组合意义可以看出

\[f(k)=\sum_{i=k}^{n}{n\choose i}g(i)\]
那就可以二项式反演了，有

\[\begin{aligned}    g(k) = \sum_{i=k}^n (-1)^{i-k} \binom{i}{k} f(i) = \sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n}{i} (2^{n-i} - 1)\end{aligned}\]
预处理阶乘及其逆元，阈值为求 \(2^{n-i} - 1\)，复杂度 \(O(n\log n)\)。
P4859 已经没有什么好害怕的了

给定 \(n,k\)，和两个长度为 \(n\) 的数列。求第一个数列与第二个数列的数两两配对，第一个数列的数大于第二个数列的数的对数恰好等于 \(\frac{n+k}{2}\)  的配对方案数。\(n+k\) 为奇数时输出0。复杂度不高于 \(O(n^2)\)。
我们称“第一个序列中的某个数与第二个序列中某个数匹配，第一个序列中的这个数比第二个序列中的这个数大”为“一次贡献”
由于复杂度阈值很高，可以考虑DP。同时可以发现两个序列中元素的顺序并不重要，因此先从小到大排序，然后双指针预处理出第二个序列中有多少个数能和第一个序列中的第 \(i\) 个数产生贡献。
然后设 \(f_{i,j}\) 表示考虑排序后的第一个序列的前 \(i\) 个数 钦定 有 \(j\) 次贡献的方案数（这里钦定的意思是要求至少 \(j\) 对数对应，这 \(j\) 组数是确定好了的，其余不作要求，这其余的数的排列方式也不记入方案数）。
发现这个东西很好DP。有

\[f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times (d_i-(j-1))\]
边界条件为 \(f_{0,0}=1\)。其中 \(d_i\) 表示前面预处理出来的第二个序列中有多少个数能和第一个序列中的第 \(i\) 个数产生贡献。注意此时的两个序列都是有序的。
这个东西可以很好地在组合意义上感性理解。需要再次强调的是，没有被选择来产生贡献的数的任何贡献与方案数都不会被统计，这里的“钦定”与“至少”是类似的意思。
然后考虑设 \(g(x)\) 表示整个第一个序列有至少 \(x\) 个贡献的总方案数。注意 \(g(x)\) 与 \(f_{n,x}\) 的区别在于我们计算了“没有被选择来产生贡献的数的方案数”。这里其贡献并没有被考虑在内。
依照这个，我们可以写出其与 \(f_{n,x}\) 的关系：

\[g(x)=(n-x)!f_{n-x}\]
这样写式子可能还清晰一点。前面的系数就是没有被选择来贡献的数与第二个序列随机选择的方案数。
然后发现其与我们要求的 \(ans_k\)（表示恰好 \(k\) 次贡献。这里的 \(k\) 已经被定义为开头的 \(\frac{n+k}{2}\) 了）有非常紧密的联系。实际上就是二项式反演的式子：

\[\begin{aligned}    g(k) = \sum_{i=k}^n \binom{i}{k} f(i)\end{aligned}\]
那就可以直接反演，有

\[\begin{aligned}    f(k) = \sum_{i=k}^n (-1)^{i-k} \binom{i}{k} g(i)\end{aligned}\]
直接做即可。复杂度阈值在DP，总复杂度 \(O(n^2)\)。
code

没什么细节。
点击查看代码[code]#includeusing namespace std;#define int long longconst int p=1e9+9,N=3005;int n,k,a[N],b[N],f[N][N],d[N],g[N],ans=0,fac[N],inv[N];int ksm(int x,int k){        int res=1;x=(x+p)%p;        while(k){                if(k&1) res=res*x%p;                x=x*x%p,k>>=1;        }        return res;}signed main(){        ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);        cin>>n>>k;fac[0]=inv[0]=1;memset(b,0x3f3f,sizeof(a));        if((n+k)&1){cout=1;i--) cin>>b,inv=inv[i+1]*(i+1)%p;        sort(a+1,a+n+1);sort(b+1,b+n+1);        int l=1,r=1;        while(lb[r]) {r++;continue;}d[l]=r-1;l++;}        f[0][0]=1;for(int i=1;i