各种反演

· · 个人记录

各种反演

在 \text{OI} 中反演是一种比较常见的应用，有各种形式的反演，可以用来解决一类恰好难算，至多或至少好求的问题。

莫比乌斯反演

形式一

恰好难算，倍数好算。

f(n)=\sum_{d|n} g(d) \Leftrightarrow g(n)=\sum_{d|n} \mu(d) f(\frac nd)

证明：

\begin{aligned} f(n) &=\sum_{d|n} g(d)\\ &=\sum_{d|n} \mu(d)f(\frac nd)\\ &=\sum_{d|n} \mu(d)\sum_{d'|\frac nd} g(d)\\ &=\sum_{d'|n} g(d') \sum_{d|\frac n{d'}} \mu(d)\\ \end{aligned}

根据莫比乌斯函数的性质，\sum\limits_{d|n} \mu(d)=[n=1]，所以上式中的 \sum\limits_{d|\frac n{d'}} \mu(d) 不等于 0 当且仅当 n=d'，所以有

\sum_{d'|n} g(d') \sum_{d|\frac n{d'}} \mu(d)=f(n)
形式二

恰好难算，因数好算。

f(n)=\sum_{n|d} g(d) \Leftrightarrow g(n)=\sum_{n|d} \mu(\frac dn) f(d)

第二个式子证明类似，这里省去。

例题 [P3455] ZAP-Queries

一句话题意，要求 \sum\limits_{i=1}^a\sum\limits_{j=1}^b [gcd(i,j)=n]。

直接反演

\begin{aligned} f(n)&=\sum_{n|d} g(d)=\lfloor \frac an \rfloor \lfloor \frac bn \rfloor\\ g(n) &=\sum_{n|d} \mu(\frac dn) f(d)\\ &=\sum_{n|d} \mu(\frac dn) \lfloor \frac ad \rfloor \lfloor \frac bd \rfloor\\ &=\sum_{T=1} ^{\min(\lfloor \frac an \rfloor \lfloor \frac bn \rfloor)} \mu(T) \lfloor \frac a{Tn} \rfloor \lfloor \frac b{Tn} \rfloor \end{aligned}
例题 [SDOI2017]数字表格

多组询问，求 \prod\limits_{i=1}^n\prod\limits_{j=1}^mf_{gcd(i,j)}，其中 f_i 为斐波那契数列第 i 项。

以下默认 $n\le m$，除法为整除 $$ \begin{aligned} \prod\limits_{i=1}^n\prod\limits_{j=1}^mf_{gcd(i,j)} &=\prod_{d=1}^n\prod_{i=1}^n\prod_{j=1}^m f_d^{[gcd(i,j)=d]}\\ &=\prod_{d=1}^nf_d^{\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d]}\\ &=\prod_{d=1}^nf_d^{\sum_{t=1}^n\mu(d)\frac n{td}\frac m{td}}\\ &=\prod_{d=1}^nf_d^{\sum_{d|T}^n\mu(\frac Td)\frac nT\frac mT}\\ &=\prod_{T=1}^n\Big(\prod_{d|T}^nf_d^{\mu(\frac Td)}\Big)^{\frac nT\frac mT}\\ \end{aligned} $$ 中间那坨可以 $O(n \log n)$ 预处理，然后对于每个询问可以 $\sqrt n \log n$ 做，总时间复杂度为 $O(T \sqrt n\log n)$。 #### 二项式反演 ##### 形式零 $$ f(n)=\sum_{i=0}^n (-1)^i\dbinom{n}{i}g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^i\dbinom{n}{i}f(i) $$ 非常对称，但是实际运用很少。 ##### 形式一 恰好难算，至多好算。 $$ f(n)=\sum_{i=m}^n\dbinom ni g(i)\Leftrightarrow g(n)=\sum_{i=m}^n (-1)^{n-i}\dbinom ni f(i) $$ 证明： $$ \begin{aligned} f(n) &=\sum_{i=m}^n \dbinom ni \sum_{j=m}^i (-1)^{j-i} \dbinom ijf(j)\\ &=\sum_{i=m}^n\sum_{j=i}^n(-1)^{j-i}\dbinom ni \dbinom ij f(j)\\ &=\sum_{j=m}^nf(j)\sum_{i=j}^n(-1)^{j-i}\dbinom ni\dbinom ij\\ &=\sum_{j=m}^{n}f(j)\sum_{i=j}^n(-1)^{j-i}\dbinom nj \dbinom{n-j}{i-j}\\ &=\sum_{j=m}^{n}\dbinom njf(j)\sum_{i=j}^n(-1)^{i-j} \dbinom{n-j}{i-j}\\ &=\sum_{j=m}^{n}\dbinom njf(j)\sum_{T=0}^{n-j}(-1)^T \dbinom{n-j}{T}\\ &=\sum_{j=m}^{n}\dbinom njf(j)[n-j=0]\\ &=f(n) \end{aligned} $$ ##### 形式二 恰好难算，至少好算。 $$ f(k)=\sum_{i=k}^n \dbinom ik g(i) \Leftrightarrow g(k)=\sum_{i=k}^n (-1)^{i-k}\dbinom ik f(i) $$ 证明类似，这里省去 ##### 例题 [P4859] 已经没有什么好害怕的了 题意，给定两个长度为 $n$ 的数组 $a$ 和 $b$，要求两两配对后恰好有 $k$ 组匹配满足 $a_i>b_i$。 考虑恰好难满足，但是我们可以先求出钦定有 $k$ 组匹配的方案，然后二项式反演后得到答案。 我们先将数组 $a$，$b$ 先分别从小到大排序，因为顺序不影响答案，我们设 $p_i$ 表示小于 $a_i$ 的 $b_i$ 的数量。 再设 $dp(i,j)$ 表示处理了前 $i$ 个数，有 $j$ 组匹配满足 $a_i>b_i$ 的方案数。 转移方程比较简单 $$ dp(i,j)=dp(i-1,j)+dp(i-1,j-1)\times(p_i-j+1) $$ 分别表示不匹配第 $i$ 个数和匹配第 $i$ 个数。 我们再设 $f(i)$ 表示钦定 $i$ 组匹配满足条件的方案数，$g(i)$ 表示恰好 $i$ 组匹配满足条件的方案数。 显然有 $f(k)=\sum\limits_{i=k}^n\dbinom ik g(i)$，根据之前的二项式反演式子，有 $g(k)=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom ik f(i)$，而 $f(i)=dp(n,i)\times(n-i)!$，然后就求完了。 ##### 例题 [CF285E] Positions in Permutations 在 $n$ 个数的排列中，定义完美数为满足 $|P_i-i|=1$ 的 $i$ 的数量，求长度为 $n$ 完美数恰好为 $m$ 的排列数量。 解法一 题目要求恰好，这个不好求，转换一下，设 $f(i)$ 表示钦定 $i$ 个位置满足条件的方案数， $g(i)$ 表示恰好 $i$ 个位置满足条件的方案数。还是有之前的式子 $g(k)=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom ik f(i)$，问题转换成求 $f(i)$，考虑 $Dp$。 设 $dp(i,j,0/1,0/1)$ 表示前 $i$ 个位置中，有 $j$ 个位置满足条件，第 $i$ 个数是否被选，第 $i+1$ 个数是否被选。 1. 第 $i$ 个位置满足条件 填 $i-1 \begin{aligned} dp(i,j,0,0)+=dp(i-1,j-1,0,0)\\ dp(i,j,1,0)+=dp(i-1,j-1,0,0) \end{aligned}

填 i+1

\begin{aligned} dp(i,j,0,1)+=dp(i-1,j-1,0,0)+dp(i-1,j-1,1,0)\\ dp(i,j,1,1)+=dp(i-1,j-1,0,1)+dp(i-1,j-1,1,1) \end{aligned}
  1. 第 i 个位置不满足条件 \begin{aligned} dp(i,j,0,0)+=dp(i-1,j,0,0)+dp(i-1,j,1,0)\\ dp(i,j,1,0)+=dp(i-1,j,0,1)+dp(i-1,j,1,1) \end{aligned}

则 f(i)=(dp(n,i,0,0)+dp(n,i,1,0))\times (n-i)!，然后求出 g(m) 即可。

解法二

将 i 与 P_i 分别看成 n 个点，这是张完全图，对于条件 |P_i-i|=1 转换成连边关系，就是 i 向 P_{i-1} 和 P_{i+1} 分别连特殊边，问题转换成求每个点要恰好连 1 条边，且恰好选了 m 条特殊边的方案数，对于特殊边所连成的图恰好是若干条链，我们把这些链排在一起，然后就转化成了序列问题，我们设 dp(i,j,0/1) 表示前 i 个点，连了 j 条特殊边，第 i 个点是否向 i-1 连边的方案数，转移很简单

\begin{aligned} &dp(i,j,0)=dp(i-1,j,0)+dp(i-1,j,1)\\ &dp(i,j,1)=dp(i-1,j-1,0) \end{aligned}

特别的，对于链和链之间是不能连边的。

最后 f(i)=(dp(n,i,0)+dp(n,i,1))\times(n-i)!

用解法二，我们又可以切掉一道水题 [AGC005D]~K Perm Counting，改一些条件就行了。

斯特林反演

$\begin{Bmatrix}n\\m\end{Bmatrix}$ 是第二类斯特林数，表示将 $n$ 个数划分成 $m$ 个集合的方案数。 斯特林反演也有两种形式 恰好难算，至多好算。 $$ f(n)=\sum_{i=m}^n \begin{Bmatrix}n\\i\end{Bmatrix} g(i) \Leftrightarrow g(k)=\sum_{i=m}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f(i) $$ 恰好难算，至少好算。 $$ f(k)=\sum_{i=k}^n \begin{Bmatrix}i\\k\end{Bmatrix} g(i) \Leftrightarrow g(k)=\sum_{i=k}^n(-1)^{i-k}\begin{bmatrix}i\\k\end{bmatrix}f(i) $$ 证明上面这个东西我们要先知道一些关于斯特林数的式子。 首先是下降幂和自然数幂之间的关系 $$ x^{\underline n}=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i $$ 用数学归纳法证明： $$ \begin{aligned} x^{\underline{n+1}} &=(x-n)x^{\underline n}\\ &=(x-n)\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^{i+1}-n\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum_{i=1}^{n+1}(-1)^{n-i+1}\begin{bmatrix}n\\i-1\end{bmatrix}x^{i}+n\sum_{i=0}^n(-1)^{n-i+1}\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum_{i=0}^{n+1}(-1)^{n-i+1}\begin{bmatrix}n\\i-1\end{bmatrix}x^{i}+n\sum_{i=0}^{n+1}(-1)^{n-i+1}\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum_{i=0}^{n+1}(-1)^{n+1-i}\begin{bmatrix}n+1\\i\end{bmatrix}x^i \end{aligned} $$ 下降幂和自然数幂之间的关系 $$ n^m=\sum_{i=0}^m \begin{Bmatrix}m\\i\end{Bmatrix}\dbinom ni i!=\sum_{i=0}^m \begin{Bmatrix}m\\i\end{Bmatrix}n^{\underline i} $$ 考虑组合意义，左边是将 $m$ 个球放入 $n$ 个集合的方案数，右边是枚举非空集合的数量，然后把 $m$ 个球放进去，因为集合不相同，要从 $n$ 个集合中挑出 $i$ 个，并且集合有标号，要乘上 $i!$。 然后我们要知道反转公式： $$ \begin{aligned} \sum_{i=m}^n(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix} \begin{bmatrix}i\\m\end{bmatrix}=[n=m]\\ \sum_{i=m}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix} \begin{Bmatrix}i\\m\end{Bmatrix}=[n=m] \end{aligned} $$ 考虑证明第一个式子 $$ \begin{aligned} n^m &=\sum_{i=0}^m \begin{Bmatrix}m\\i\end{Bmatrix}n^{\underline i}\\ &=\sum_{i=0}^m \begin{Bmatrix}m\\i\end{Bmatrix}\sum_{j=0}^i(-1)^{i-j}\begin{bmatrix}i\\j\end{bmatrix}n^j\\ &=\sum_{j=0}^mn^j\sum_{i=j}^m(-1)^{i-j}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}\\ \end{aligned} $$ 所以得到 $\sum\limits_{i=j}^m(-1)^{i-j}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}=[j=m]$，即上面的第一个反转公式，第二个证明类似，就是将式子反过来整即可。 然后我们就可以证明上面的斯特林反演的式子了 $$ f(n)=\sum_{i=m}^n \begin{Bmatrix}n\\i\end{Bmatrix} g(i) \Leftrightarrow g(n)=\sum_{i=m}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f(i) $$ 把右侧代入左侧 $$ \begin{aligned} f(n)& =\sum_{i=m}^n \begin{Bmatrix}n\\i\end{Bmatrix} g(i)\\ &=\sum_{i=m}^n\begin{Bmatrix}n\\i\end{Bmatrix}\sum_{j=m}^i(-1)^{i-j}\begin{bmatrix}i\\j\end{bmatrix}f(j)\\ &=\sum_{j=m}^nf(j)\sum_{i=j}^n(-1)^{i-j}\begin{Bmatrix}n\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}\\ \end{aligned} $$ 因为 $\sum_{i=j}^n(-1)^{i-j}\begin{Bmatrix}n\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}=[j=n]$，所以 $=\sum_{j=m}^nf(j)\sum_{i=j}^n(-1)^{i-j}\begin{Bmatrix}n\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}=f(n)$，所以式子成立。第二个斯特林反演的式子也同理。 ##### 例题 [雅礼集训2018] 方阵 给定一个 $n\times m$ 的矩阵，每个位置能填的数字为 $[1,c]$，求填完数后满足任意两行互不等价且任意两列互不相同的方案数。 $n,m\le 5\times 10^3

行列都有限制，比较难处理，先考虑任意两行互不等价的方案数。

设 g(m) 表示行之间互不等价，有 m 列的方案数。

考虑 g(m) 怎么计算，显然第一行的方案数为 c^m，而对于后面的每一行，只要与之前行有任意一个数不同即可，所以 g(m)=(c^m)^{\underline n}。

再考虑设 f(m) 表示行之间相互不等价且列之间相互不等价，有 m 列的方案数。

考虑 f(m) 和 g(m) 之间的关系，有 g(m)=\sum\limits_{i=0}^m \begin{Bmatrix}m\\i\end{Bmatrix} f(i)，即枚举将 m 列划分成 i 个集合的方案数求和。

那么根据斯特林反演，显然有 f(m)=\sum\limits_{i=0}^m(-1)^{m-i}\begin{bmatrix}m\\i\end{bmatrix} g(i)，然后就求完了。

预处理斯特林数是 O(n^2) 的，求出 f(m) 是 O(n)/O(n\log n) 的，所以总的时间复杂度为 O(n^2)，也可以用生成函数加多项式知识来 O(n \log n) 来预处理出第一类斯特林数的第 m 行，可以做到总的时间复杂度为 O(n \log n)，但是我并不会，也不在今天的讲题范围内，有兴趣的同学可以自行学习。