command_block 的博客

command_block 的博客

炫酷反演魔术

posted on 2020-05-06 17:34:07 | under 算法 |

最近你可能在本Blog看到许多这样的小记,这完全属于省选之前的游击战术,内容不保证严谨,也不保证大多数人能看懂。

如果省选过后有时间我会来仔细更新并且把这些文字去掉的。


广告(配合食用) : 多项式计数杂谈 (万字长文,公式恐惧症患者请谨慎入坑)

本文将介绍一些 OI 中常见反演的证明和应用。

1.基本反演推论

  • $\color{blue}\bf\Delta$ 反演本质

首先,“反演”这个词,就是指 : 两个函数(数列)之间的双向(求和)关系。

比如说 $F[n]=\sum\limits_{i=0}^nG[i]$ ,即前缀和。

那么反过来 $G[n]=F[n]-F[n-1]$ ,即差分。

一对关系就称作反演关系。

我们定义一个矩阵 $A$ 为关系矩阵,用于描述求和关系 $F[n]=\sum\limits_{i=0}^∞A[n,i]G[i]$。

也就是说,$F=G*A$。

已知 $G$ 求算 $F$ 是可行的。现在我们要由 $F$ 求算 $G$。

不难想到,求关系矩阵 $A$ 的逆矩阵 $A^{-1}$ ,然后则有 $G=A^{-1}F$。

比如,上面的前缀和的关系矩阵即为 $A[n,i]=[i\leq n]$。

即 $F[n]=\sum\limits_{i=0}^∞[i\leq n]G[i]=\sum\limits_{i=0}^nG[i]$。

那么相应的,差分的关系矩阵 $B[n,i]=\begin{cases}-1&(i=n-1)\\1&(i=n)\end{cases}$

即 $G[n]=\sum\limits_{i=0}^∞B[n,i]F[i]=F[n]-F[n-1]$。

我们把两个矩阵乘起来试试看:

$(A*B)[n,m]=\sum\limits_{i=0}^∞A[n,i]B[i,m]=\sum\limits_{i=n}^∞[m=i]-[m=i-1]=[n=m]$

也就是说,$A*B=I$ ,即矩互逆。

$\color{blue}\text{定理}:$ 两个互为反演的关系矩阵互逆

那么我们就可以使用矩阵相关的方法来分析反演了。

有时候这个求和不是从 $0$ 开始的,大家注意一下就好了。

  • $\color{blue}\bf\Delta$ 反演证明的常见迁移方法

    • 一对互逆的矩阵转置之后仍然互逆(显然法)。

    • 一对互逆的矩阵分别数乘 $c\ (c≠0)$ 后仍然互逆。

    • $-1$ 的幂可以在反演系数中移动。

      $$\sum\limits_{t=0}(-1)^{n-t}A_{n,t}B_{t,m}=[n=m]\quad \Longleftrightarrow \quad \sum\limits_{t=0}(-1)^tA_{n,t}(-1)^mB_{t,m}=[n=m]$$

    数乘 $(-1)^{m-n}$ ,然后分成两部分即可。

    可以使得只有一边有 $-1$ 的幂的形式和两边都有的形式互推。

  • $\color{blue}\bf\Delta$ 多个维度的反演叠加

其实是基于以下事实:

假如有:

$F(n)=\sum\limits_{i=0}A_1[n,i]G(i)\Leftrightarrow G(n)=\sum\limits_{i=0}B_1[n,i]F(i)$

$F(n)=\sum\limits_{i=0}A_2[n,i]G(i)\Leftrightarrow G(n)=\sum\limits_{i=0}B_2[n,i]F(i)$

即任意的两个反演关系。

根据上问我们知道矩阵 $(A_1,B_1),(A_2,B_2)$ 分别互逆。

那么有如下结论(二维情况):

$$F(n,m)=\sum\limits_{i=0}\sum\limits_{j=0}A_1[n,i]A_2[m,j]G(i,j)\quad\Longleftrightarrow \quad G(n,m)=\sum\limits_{i=0}\sum\limits_{j=0}B_1[n,i]B_2[m,j]F(i,j)$$

也即 : 多维反演,系数$=$每个维度的反演系数之

$\color{blue}\text{证明:}$

构造新的大矩阵 $A[(n_1,n_2),(i_1,i_2)]=A_1[n_1,i_1]A_2[n_2,i_2]$ ,$B$ 类似。

欲证 $A*B=I$ ,即证 $(A*B)[(n_1,n_2),(m_1,m_2)]=[(n_1,n_2)=(m_1,m_2)]$

${\rm LHS}=\sum\limits_{(i_1,i_2)}A[(n_1,n_2),(i_1,i_2)]B[(i_1,i_2),(m_1,m_2)]$

$=\sum\limits_{(i_1,i_2)}A_1[n_1,i_1]A_2[n_2,i_2]B[i_1,m_1]B[i_2,m_2]$

$=\sum\limits_{i_1}A_1[n_1,i_1]B_1[i_1,m_1]\sum\limits_{i_2}A_2[n_2,i_2]B_2[i_2,m_2]$

$=[n_1=m_1][n_2=m_2]={\rm RHS}$

这个证明可以很容易地推广到更多维。

  • 反演花名册

反演是帮助我们转化问题的利器,然而反演关系的构造往往并不容易。

下面列出的是一些经典的反演。

  • 二项式反演

  • 莫比乌斯反演

  • Min-Max反演(容斥)

  • 斯特林反演

  • 集合反演

  • 单位根反演

我们来一一介绍吧 :

2.二项式反演

由于二项式系数在计数问题中十分常见,很多芝士需要二项式反演来支持。

而且这玩意相对不那么困难,可以用来练手,先熟悉一下反演的风格。

我尽量把证明写得详细一点。

形式 :

$$F(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}G(i)\quad\Longleftrightarrow\quad G(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}F(i)$$

非常对称。即 $A[n,i]=(-1)^i\dbinom{n}{i}$ 这个矩阵是自逆的。

  • (经典代数)$\color{blue}\text{证明:}$ $(A*A)[d,t]=\sum\limits_{i=1}^∞A[d,i]A[i,t]$

    $=\sum\limits_{i=t}^d(-1)^i\dbinom{d}{i}(-1)^t\dbinom{i}{t}$

    $=(-1)^t\sum\limits_{i=t}^d(-1)^i\dfrac{d!i!}{i!(d-i)!t!(i-t)!}$

    • 我们想办法提取一个$\dbinom{d}{t}$的常量出来

    后面部分$=\dfrac{d!}{t!(d-t)!}\dfrac{(d-t)!}{(d-i)!(i-t)!}$

    注意到 $i-t=(d-t)-(d-i)$,得到:

    $=\dbinom{d}{t}\dfrac{(d-t)!}{(d-i)!((d-t)-(d-i))!}=\dbinom{d}{t}\dbinom{d-t}{d-i}$

    原式$=(-1)^t\dbinom{d}{t}\sum\limits_{i=t}^d(-1)^i\dbinom{d-t}{d-i}$

    平移使得下界为 $0$ ( 把每个 $i$ 减去 $t$ ) 得到

    $\sum\limits_{i=t}^d(-1)^i\dbinom{d-t}{d-i}=\sum\limits_{i=0}^{d-t}(-1)^{i+t}\dbinom{d-t}{d-t-i}$

    提取常量,使用二项式系数的对称性

    $=(-1)^t\sum\limits_{i=0}^{d-t}(-1)^{i}\dbinom{d-t}{i}$

    由二项式定理得:

    $=(-1)^t(1-1)^{d-t}$

    原式$=(-1)^{t+t}\dbinom{d}{t}(1-1)^{d-t}=[d=t]$

    于是 $A*A=I$ ,反演成立。

使用基本反演推论移动 $-1$ 的幂,马上就能得到另外的一种形式 :

$$F(n)=\sum\limits_{i=0}^n\dbinom{n}{i}G(i)\quad\Longleftrightarrow\quad G(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}F(i)$$

这个形式更为常用。因为做题的时候不会凑出 $-1$ ,而这个东西左边是没有 $-1$ 的。

还有另一种使用指数生成函数的证明方法。

  • (EGF)$\color{blue}\text{证明:}$

    $F[n]=\sum\limits_{i=0}^n\dbinom{n}{i}G[i]$

    $\dfrac{F[n]}{n!}=\sum\limits_{i=0}^n\dfrac{1}{(n-i)!}\dfrac{G[i]}{i!}$

    辨识出卷积形式,以及 $e^x=\sum\limits_{i=0}\dfrac{x^i}{i!}$

    $F*e^x=G\quad\Longleftrightarrow\quad G=F*e^{-x}$

    $\dfrac{G[n]}{n!}=\sum\limits_{i=0}^n\dfrac{(-1)^{n-i}}{(n-i)!}\dfrac{F[i]}{i!}$

    $G[n]=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}F[i]$

    非常简洁,建议熟悉生成函数理论的同学使用这种。

使用基本反演推论转置形式 的矩阵(简单地把两个维度交换),能够得到形式 :

$$F(n)=\sum\limits_{i=n}\dbinom{i}{n}G(i)\quad\Longleftrightarrow\quad G(n)=\sum\limits_{i=n}(-1)^{i-n}\dbinom{i}{n}F(i)$$

( 为什么不转置①?因为那个矩阵是不对称的 )

实际题目中超出一定范围的 $F,G$ 都是 $0$,所以不用在意上界问题。

移动 $-1$ 的幂,又能得到另外的一种形式 :

$$F(n)=\sum\limits_{i=n}(-1)^i\dbinom{i}{n}G(i)\quad\Longleftrightarrow\quad G(n)=\sum\limits_{i=n}(-1)^{i}\dbinom{i}{n}F(i)$$

至此,我们已经集齐了二项式反演的四种形式。

接下来,让我们看看经典应用。

  • $\color{blue}\bf\Delta$ 错排问题

可以去这里提交 : P1595 信封问题

一个排列 $P_{1...n}$ ,满足 $P_i≠i$ (每个数都不在自己的位置上)称为错位排列,问这样的排列数。

我们设 $D[n]=$ 长度为 $n$ 的错位排列数。

正面求解问题较为困难,我们先从 $D$ 出发,看看能得到什么求和关系。

考虑所有的排列,分别可能有 $0,1,2...n$ 个数不在自己的位置上。分别统计每一种的方案数。

假如有 $k$ 个不在自己的位置上,那我们任意选定 $k$ 个位置,然后将它们严格错排,剩下不动,即可不重不漏。

所以 $n!=\sum\limits_{i=0}^n\dbinom{n}{i}D[i]$

多么眼熟啊! 这不就是二项式反演吗?

使用(形式②)反演公式能够得到 :

$D[n]=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}i!=\sum\limits_{i=0}^n(-1)^{n-i}\dfrac{n!}{(n-i)!}$

$=n!\sum\limits_{i=0}^n\dfrac{(-1)^{n-i}}{(n-i)!}=n!\sum\limits_{i=0}^n\dfrac{(-1)^i}{i!}$

我们只需要预处理阶乘(逆元)以及 $S[n]=\sum\limits_{i=0}^n\dfrac{(-1)^i}{i!}$ ,就能 $O(n)$ 求解 $D[1...n]$ 了。

通过这个小问题,可以发现,反演的应用难点并不在于公式本身,而在于拼凑出和公式对应的组合意义。

还有另一种更加易于理解,也更常用的推导方法 : 钦定法

我们称满足 $P_i=i$ 的 $i$ 为“不动点”。

设 $g(n,k)$ 为 有 $k$ 个不动点的长度为 $n$ 的排列个数。

设 $f(n,k)$ 为钦定 $k$ 个不动点后,满足条件的长度为 $n$ 的排列个数。

对于 $g(n,m)$ 中的一种排列,有 $\dbinom{m}{k}$ 种方案钦定出其中 $k$ 个不动点。

则有 $f(n,k)=\sum\limits_{m=k}\dbinom{m}{k}g(n,m)$。

这就是和二项式反演完美契合的组合意义!使用反演公式可得 :

$g(n,m)=\sum\limits_{k=m}(-1)^{k-m}\dbinom{k}{m}f(n,k)$

求 $f(n,k)$ 则简单得多,因为其对未钦定的部分没有任何限制

先选出 $k$ 个不动点,方案数为 $\binom{n}{k}$。选完之后,不动点处填的数已经确定,其余部分还可以任意排列,方案数为 $(n-k)!$

则有 $f(n,k)=\binom{n}{k}(n-k)!=n!/k!$

代入可得 $g(n,m)=\sum\limits_{k=m}(-1)^{k-m}\dbinom{k}{m}n!/k!$

我们要求的 $D[n]=g(n,0)=\sum\limits_{k=m}(-1)^{k}n!/k!=n!\sum\limits_{k=m}\dfrac{(-1)^{k}}{k!}$

(当 $m=0$ 时二项式反演退化为经典容斥)

  • 形式②NTT加速二项式反演

已知 $F[0...n]$ 且 $G[n]=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}F(i)$

按照上式暴力求和计算 $G[0...n]$ 的话需要 $O(n^2)$ 的复杂度。

在前面我们已经辨认出卷积 $G=F*e^{-x}$ ,使用 NTT 加速即可做到 $O(n\log n)$。

题目 : P4491 [HAOI2018]染色

题解 P4491 【[HAOI2018]染色】

  • 形式$④$ :

  • $\color{blue}\bf\Delta$ P6478 [NOI Online #2 提高组]游戏

    题意 : 有一棵 $2m$ 个点的有根树,其中有 $m$ 个黑点, $m$ 个白点。

    将黑点和白点分别标号 $1...m$。

    如果第 $i$ 个黑点和第 $i$ 个白点之间有祖孙关系,则记为好事件。(容易发现一共只有 $m$ 个事件)

    求好事件的个数恰好为 $0...m$ 的(指定顺序的)方案数。$m\leq 2500$。

直接计算相当困难,我们发现“恰好”是最大的障碍,因为其不仅要求有 $k$ 个好事件,还要求其余的都不是好事件。

考虑打破“恰好”的限制,改为 : 钦定 $k$ 个好事件,其余的事件放任自流。

这样的好处是,对于其余事件的影响被忽视了,我们只需要关注好事件。

设 $f[u][k]$ 为 $u$ 子树中(钦定)产生了 $k$ 个好事件的方案数。

首先不考虑根,好事件的叠加就是经典的加法卷积。

令 $v$ 为 $u$ 的直接儿子。

则有 $f_*[u][k]=\sum\limits_{i=0}^kf[u][i]*f[v][k-i]$

一个经典的结论是,使用子树大小剪枝即可做到 $O(n^2)$ 的复杂度。

然后考虑根和子树能够产生的好事件。不妨设根为黑色,白色类似。

设 $s0[u]$ 为子树内白点个数, $s1[u]$ 为黑点个数。

则有 $f_[u][j+1]$ += $f[u][j]*(s0[u]-j)$

意思就是 : 从剩余的 $s0[u]-j$ 个白点中,找一个和根(黑点)匹配。

设 $F[k]$ 为钦定 $k$ 个好事件,其余的事件放任自流的方案数。即为最后的 $f[1][0...m]$ 。

设 $G[k]$ 为恰好有 $k$ 个好事件的方案数。即为答案。

有 $\dbinom{i}{k}$ 种方案从 $i$ 个好事件中钦定 $k$ 个,则有。

$F[k]=\sum\limits_{i=k}^n\dbinom{i}{k}G[i]$

二项式反演可得

$G[k]=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}F[i]$

题目允许我们暴力 $O(n^2)$ 计算这个式子。

3.莫比乌斯反演

这一类反演关系非常特殊,可以用迪利克雷卷积来描述。

莫比乌斯反演与数论函数

4.Min-Max反演(容斥)

Min-Max容斥小记

5.斯特林反演

基本形式的证明请见 : “多项式计数杂谈”,这里直接给出四种形式。

$$F(n)=\sum\limits_{i=0}^n\begin{Bmatrix}n \\ i\end{Bmatrix}G(i)\quad\Longleftrightarrow\quad G(n)=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n \\ i\end{bmatrix}F(i)$$

$$F(n)=\sum\limits_{i=0}^n(-1)^{n-i}\begin{Bmatrix}n \\ i\end{Bmatrix}G(i)\quad\Longleftrightarrow\quad G(n)=\sum\limits_{i=0}^n\begin{bmatrix}n \\ i\end{bmatrix}F(i)$$

$$F(n)=\sum\limits_{i=n}\begin{Bmatrix}i \\ n\end{Bmatrix}G(i)\quad\Longleftrightarrow\quad G(n)=\sum\limits_{i=n}(-1)^{i-n}\begin{bmatrix}i \\ n\end{bmatrix}F(i)$$

$$F(n)=\sum\limits_{i=n}(-1)^{i-n}\begin{Bmatrix}i \\ n\end{Bmatrix}G(i)\quad\Longleftrightarrow\quad G(n)=\sum\limits_{i=n}\begin{bmatrix}i \\ n\end{bmatrix}F(i)$$

  • 例题 : [2018雅礼集训1-16] 方阵

    提交可以去 Vjudge TopCoder-13444 CountTables

    题意 : 给出一个 $n×m$ 的矩阵,每个位置可以填上 $[1,c]$ 中的任意整数。

    要求填好后任意两行互不等价,且任意两列互不等价。两行或两列等价当且仅当对应位置完全相同,求方案数。

    $n,m\leq 4000$.

行和列之间的限制有交,不便处理。不妨先只考虑行的限制。

设 $f(n,m)$ 为行不等价的情况下, $n×m$ 的矩形的个数。

任意一个行的方案数为 $c^m$ ,共有 $n$ 个行,易得 $f(n,m)=(c^m)^{\underline n}$

设 $g(n,m)$ 为行和列都不等价的情况下, $n×m$ 矩形的个数。即为答案。

能得到 :

$$f(n,m)=\sum\limits_{i=1}^m\begin{Bmatrix}m \\ i\end{Bmatrix}g(n,i)$$

组合意义 : 枚举 $m$ 列分成了 $i$ 个互不等价的集合,再将这 $m$ 列分配到这些集合中去。

实际上就是考虑 “划分”。将等价的部分划分到一起,即蕴含全部不等价的方案。

使用斯特林反演可得 :

$$g(n,m)=\sum\limits_{i=1}^m(-1)^{m-i}\begin{bmatrix}m \\ i\end{bmatrix}f(n,i)$$

评测记录

咕了。找不到题做。

6.集合反演

莫比乌斯反演就是在因子多重集上的反演。某种意义上讲,是这套理论的子集。

所以,很多莫反的技巧可以迁移过来。

  • $\color{blue}\bf\Delta$ 拆交集

    莫反中 $\gcd$ 就相当于取交集,注意到 $[d|(x,y)]=[d|x][d|y]$.

    类似地也有 $[S⊆(X∩Y)]=[S⊆X][S⊆Y]$ , 可以把交集变得独立。

  • $\color{blue}\bf\Delta$ 得到容斥系数

    由 $\sum\limits_{d|n}\mu(d)=[n=1]$ ,我们才能莫比乌斯反演.

    我们同样也需要 $\sum\limits_{S⊆U}\mu(S)=[U=\varnothing]$ ,不难发现 $\mu(x)=(-1)^{|S|}$ 即可。这是个经典构造 : 奇负偶正。

    • 理解 : 设全集大小为 $n$ ,考虑不同大小的子集的方案数以及贡献。

      注意到 $\sum\limits_{i=0}^n\dbinom{n}{i}(-1)=(1-1)^n=[n=0]$

    • 这个容斥系数引出了憨逼子集反演 :

      若有 $F(U)=\sum\limits_{S⊆U}f(S)$ ,即子集求和。

      $f(S)=\sum\limits_{S⊆U}[S-U=\varnothing]f(S)$

      $=\sum\limits_{S⊆U}\sum\limits_{T\subseteq S-U}(-1)^{|T|}f(S)$

      注意到 $T\subseteq S-U$ 类似于 $t|\frac{s}{u}$ ,那么交换和式之后就有

      $=\sum\limits_{T\subseteq U}(-1)^{|T|}\sum\limits_{U⊆S-T}f(S)$

      $=\sum\limits_{T\subseteq U}(-1)^{|T|}F(S-T)$

      则导出

      $$F(S)=\sum\limits_{T⊆S}f(T)\ \Longleftrightarrow\ f(S)=\sum\limits_{T⊆S}(-1)^{|S-T|}F(S)$$

      其实就是子集卷积上 $\mu$。

      类似地有

      $$F(S)=\sum\limits_{S⊆T}f(T)\ \Longleftrightarrow\ f(S)=\sum\limits_{S⊆T}(-1)^{|T-S|}F(S)$$

    考虑推广到多重集合,$\sum\limits_{S⊆U}\mu(S)=[U=\varnothing]$ 如何保持呢?

    注意到多重集合肯定不是空集,我们只需要简单地令含有重复的元素的集合贡献为 $0$ 即可。

    那么有 $\mu(S)=(-1)^{|S|}[S\text{中无重复元素}]$

    其实数论中的莫比乌斯函数就是这个原则的体现。

  • $(3)$ 考虑到莫比乌斯反演中有 $F*I*\mu=F$ 即 $F(n)=\sum\limits_{d|n}\sum\limits_{t|d}\mu(\frac{d}{t})F(t)$

    类似地有$F(U)=\sum\limits_{S⊆U}\sum\limits_{P⊆S}\mu(|S-P|)$ 即 $f(P)=\sum\limits_{S⊆U}\sum\limits_{P⊆S}(-1)^{|S|-|P|}f(P)$

    和 $(1)$ 配合用于拆交集。和莫反中拆 $\rm gcd$ 是一个道理。

仍然找不到题目,只有一道 : P5206 [WC2019] 数树

7.单位根反演

单位根反演小记