二项式反演
本质上是某种容斥。
结论为：
\[f_i = \sum_{j=0}^i(-1)^j\binom{i}{j}g_j\Leftrightarrow g_i = \sum_{j=0}^i(-1)^j\binom{i}{j}f_j \]更常用的形式是
\[f_i = \sum_{j=0}^i \binom{i}{j}g_j\Leftrightarrow g_i = \sum_{j=0}^i(-1)^{i-j}\binom{i}{j}f_j \]证明第二个式子（EGF 证法）：
记 \(f\) 的指数生成函数为 \(F(x)\)，\(g\) 的指数生成函数为 \(G(x)\)。
那么
实际上还有一种形式：
\[f_i = \sum_{j=i}(-1)^j\binom{j}{i}g_j\Leftrightarrow g_i = \sum_{j=i}(-1)^j\binom{j}{i}f_j \]或者写成：
\[f_i = \sum_{j=i}\binom{j}{i}g_j\Leftrightarrow g_i = \sum_{j=i}(-1)^{i-j}\binom{j}{i}f_j \]错排问题
长度为 \(n\) 的排列 \(p\) 若对于 \(1\le i\le n\) 满足 \(i\not= p_i\)，称它为一个错位排列。
将长度为 \(n\) 的错位排列数记为 \(D_n\)。
需要快速地求出某一 \(D_n\)。
对于所有长度为 \(n\) 的排列 \(p\)，有 \(k\) 个 \(i\) 满足 \(p_i\not= i\) 的排列 \(p\) 的个数为 \(\binom{n}{k}D_k\)。
考虑枚举 \(k\) 即有：
\[n! = \sum_{i=0}^n\binom{n}{k}D_k \]套用反演结论即有
\[D_n = \sum_{i=0}^n(-1)^{n-i}\binom{n}{k}k!=n!\sum_{i=0}^n(-1)^{i}\frac1{i!} \]QOJ#5826 GDKOI2023TG D1T2
求有几个长度为 \(n\) 的排列 \(p\) 满足 \(\forall 1\le i\le m, p_i>m\) 且 \(\forall 1\le i\le n, p_i\not=i\)， \(\operatorname{mod} 998244353\)。
不会正解，推个基本的式子。
考虑先在 \([m+1, n]\) 点 \(m\) 个数填在前 \(m\) 个位置上，然后将剩下除 \([1, m]\) 的 \(n-2m\) 个数填掉，最后把 \([1, m]\) 直接填进去。
发现第一步会有一个 \(\frac{(n-m)!}{(n-2m)!}\) 的系数，第三步会有一个 \(m!\) 的系数，把这两步系数的乘积记为 \(k\)，而第二步的系数不太好计算，类似于原版错排问题。
枚举第二步中 \(p_i=i\) 的位置的个数：
\[k\binom{n-m}{n-2m}=\sum_{i=0}^{n-2m}\binom{n-2m}{i}f_i \]令 \(l = n-2m\)，那么
\[k\binom{l+m}{l}=\sum_{i=0}^{l}\binom{l}{i}f_i \]反演得
\[f_l = k\sum_{i=0}^l(-1)^{l - i}\binom{l}{i}\binom{i+m}{i} \]BZOJ3622 已经没什么好害怕的了
给定两个长度为 \(n\) 的序列 \(a,b\)，将 \(a\) 与 \(b\) 两两配对，求 \(a\) 比 \(b\) 大的组恰好有 \(k\) 个的方案数。
\(n\le 2000\)
容斥dp
恰有 \(k\) 组不太好求，考虑用容斥变为钦定 \(k\) 组，其余随意。
用 \(g_i\) 表示恰有 \(i\) 组的方案数，\(f_i\) 表示钦定 \(i\) 组的方案数，那么：
\[f_k(n-k)! = \sum_{i=k}^n\binom{i}{k}g_i \]这个式子珂能不太好理解，左边的意思是钦定 \(k\) 对，其余任选；右边的意思是对于每个 \(i\ge k\) 都可以点 \(k\) 组来钦定，因此这个式子是正确的。
这个式子可以直接套另一种二项式反演。
\[f_k(n-k)! = \sum_{i=k}^n\binom{i}{k}g_i \]考虑将 \(f\) 数组 dp 出来：
\(f_{i,j}\) 表示当前 dp 到 \(i\)，已经钦定了 \(j\) 对的方案数。
我们将 \(a, b\) 分别降序排序，方便 dp。
用 \(mx_i\) 表示 \(a_i\) 可以匹配的数的个数，那么可以轻易写出状态转移方程：
\[f_{i, j}=f_{i-1, j} + (mx_i-j+1)f_{i-1, j-1} \]时间复杂度 \(\mathcal{O(n^2)}\)。
Min-Max 反演
首先由二项式定理可以得到一个式子
\[\sum_{T\subseteq S}(-1)^{|T|} = [S=\varnothing] \]这个式子是好证明的：
\[\sum_{T\subseteq S}(-1)^{|T|} = \sum_{i=0}^{|S|}\binom{|S|}{i}(-1)^i = (1-1)^{|S|} = [S = \varnothing] \]Min-Max 反演的结论式为：
\[\max S = \sum_{T\subseteq S \land T \not= \varnothing} (-1)^{|T| - 1}\min T\\ \min S = \sum_{T\subseteq S \land T \not= \varnothing} (-1)^{|T| - 1}\max T \]证明第一个式子，第二个式子的证明是类似的
\[\begin{split} &\max S \\ =&\sum_{x\in S}x[\{y|y>x\} = \varnothing]\\ =&\sum_{x\in S}x\sum_{T\subseteq\{y|y>x\}}(-1)^{|T|}\\ =&\sum_{T\in S \land T \not= \varnothing} (-1)^{|T| - 1}\min T \end{split} \]期望形式同样成立：
\[E(\max S) = \sum_{T\subseteq S \land T \not= \varnothing} (-1)^{|T| - 1}E(\min T)\\ E(\min S) = \sum_{T\subseteq S \land T \not= \varnothing} (-1)^{|T| - 1}E(\max T) \]Luogu P3175 [HAOI2015] 按位或
考虑对于每一位分别考虑，答案就是每一位第一次出现的时间的最大值。
最大值是不好处理的，使用 Min-Max 反演转化成最小值。
\(\min S = \dfrac1{\sum_{T\cap S\not ={\varnothing}}p_{T}}\)
发现交不为空实际上就是状压后位与起来不等于 \(0\)，这个不好求，考虑求出位与起来等于 \(0\) 的和减一下就好了，位与起来为 \(0\) 也就是将 \(S\) 取反后 \(T\) 为 \(S\) 的子集，直接高维前缀和即可。
还有一道很神的题，这里是题解： Luogu P5643 [PKUWC2018]随机游走
Min-Max 反演推广——Kth Min-Max 反演
如何将一个集合中的第 \(k\) 大转化成子集 \(\min\) 呢？
发现 Min-Max 中用的结论是
\[\sum_{T\subseteq S}(-1)^{|T|} = [S=\varnothing] \]如果找到函数 \(f(x)\) 使得 \( \sum_{T\subseteq S}f(|T|) = [|S|=k-1]\)，就可以得出 Kth Min-Max 反演的式子。
我推的柿子：
\[\begin{split} &\sum_{T\subseteq S}f(|T|) = [|S|=k-1]\\ &\sum_{i=0}^{|S|}\binom{|S|}{i}f(i) = [|S|=k-1] \end{split} \]二项式反演得
\[f(x) = \sum_{i=0}^x(-1)^{x-i}\binom{x}{i}[i=k-1]=(-1)^{x-k+1}\binom{x}{k-1} \]于是可以写出 Kth Min-Max 反演的式子：
\[\operatorname{kth-max}S=\sum_{T\subseteq S\land T\not ={\varnothing}}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min T\\ \operatorname{kth-min}S=\sum_{T\subseteq S\land T\not ={\varnothing}}(-1)^{|T|-k}\binom{|T|-1}{k-1}\max T \]期望形式同样成立。
Luogu P4707 重返现世
首先用 Kth Min-Max 反演：
\[E(\operatorname{kth-max}S) = \sum_{T\subseteq S\land T\not ={\varnothing}}(-1)^{|T|-k}\binom{|T|-1}{k-1}E(\min T)\\ \]注意到此处的 \(k\) 和题面中意义不同，实际上是 \(n-k+1\)，所以非常小。
若用 \(\operatorname{sum}{S}\) 表示集合 \(S\) 中所有元素的和，则 \(E(\min T) = \dfrac m{\operatorname{sum}T}\)，此处两个 \(T\) 第一个是表示第一次出现的时间集合，第二个是表示出现概率 \(p_i\) 的集合。
于是柿子变为：
\[E(\operatorname{kth-max}S) = (-1)^k\sum_{T\subseteq S\land T\not ={\varnothing}}(-1)^{|T|}\binom{|T|-1}{k-1}\dfrac m{\operatorname{sum}T}\\ \]考虑 dp 求出这个和式。
可以对于所有的 \(|T|\) 和 \(\operatorname{sum}T\) 求出其方案数，这样就可以计算了。这个是好容易用 dp 解决的，一个一个数考虑加不加入即可，但这样的时间复杂度是 \(\mathcal{O}(n^2m)\) 的，且没有用到 \(k\) 特别小的条件。
考虑减少状态，发现 \(\operatorname{sum}T\) 不好消去，只能把 \(|T|\) 这一维消去。
那么需要对于每个 \(j = \operatorname{sum}T\) 求出
\[\sum_{\operatorname{sum}T=j} (-1)^{|T|}\binom{|T|-1}{k-1} \]考虑加入一个数时（也就是 \(|T|\) 增加 \(1\) 时）这个柿子会发生什么变化，可以发现 \((-1)^{|T|}\) 会取反且 \(\binom{|T|-1}{k-1}\) 会变成 \(\binom{|T|}{k-1}\)，这个二项式系数发生了什么变化呢，观察不到 \(\binom{|T|}{k-1} = \binom{|T|-1}{k-1} + \binom{|T|-1}{k-2}\)，于是可以在 dp 中记录 \(k\) 这一维进行递推。
\(f_{i, j, d}\) 表示当前 dp 到 \(i\) 时的 \(\sum\limits_{\operatorname{sum}T=j} (-1)^{|T|}\binom{|T|-1}{d}\)，那么可以写出状态转移方程：
\[\begin{split} f_{i, j, d} &\gets f_{i-1, j, d}\\ f_{i, j, d} &\gets -(f_{i-1, j-p_i, d} + f_{i-1, j-p_i, d-1}) \end{split} \]这样做时间复杂度是 \(\mathcal{O}(nmk)\)，空间上可以将第一维滚掉。
\[\mathcal{-END-} \] 标签：Min,Max,sum,反演,varnothing,binom,subseteq,operatorname From： https://www.cnblogs.com/0922-Blog/p/binom_and_minmax.html