炫酷反演魔术

command_block · 2020-05-06 17:34:07 · 个人记录

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

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

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

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

1.基本反演推论

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

比如说 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 ，即矩互逆。

那么我们就可以使用矩阵相关的方法来分析反演了。有时候这个求和不是从 $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)

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

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

可以去这里提交 : 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]染色】

形式④ :
**题意** : 有一棵 $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) 计算这个式子。

补充习题 :
- CF1228E Another Filling the Grid
二维容斥，也可以从二维二项式反演理解。

进阶版 : CF997C Sky Full of Stars
- [数学记录]P4921 烧情侣
- 题解 P5339 【[TJOI2019]唱、跳、rap和篮球】
- P5400 [CTS2019]随机立方体
题解 P5400 【[CTS2019]随机立方体】
- [数学记录]P5401 [CTS2019]珍珠

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] 中的任意整数。

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

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

设 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.集合反演

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

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

莫反中 $\gcd$ 就相当于取交集,注意到 $[d|(x,y)]=[d|x][d|y]$. 类似地也有 $[S⊆(X∩Y)]=[S⊆X][S⊆Y]$ , 可以把交集变得独立。
由 $\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.单位根反演

单位根反演小记