炫酷反演魔术

最近你可能在本`Blog`看到许多这样的小记,这完全属于省选之前的游击战术,内容不保证严谨,也不保证大多数人能看懂。 如果省选过后有时间我会来仔细更新并且把这些文字去掉的。 ------------ **广告**(配合食用) : [多项式计数杂谈](https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan) (万字长文,公式恐惧症患者请谨慎入坑) 本文将介绍一些 `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 信封问题](https://www.luogu.com.cn/problem/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]染色](https://www.luogu.com.cn/problem/P4491) [题解 P4491 【[HAOI2018]染色】](https://www.luogu.org/blog/command-block/solution-p4491) - **形式$④$** : - $\color{blue}\bf\Delta$ [P6478 [NOI Online #2 提高组]游戏](https://www.luogu.com.cn/problem/P6478) **题意** : 有一棵 $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](https://www.luogu.com.cn/problem/CF1228E) 二维容斥，也可以从二维二项式反演理解。 进阶版 : [CF997C Sky Full of Stars](https://www.luogu.com.cn/problem/CF997C) - [[数学记录]P4921 烧情侣](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-p4921p4931-shao-qing-lv) - [题解 P5339 【[TJOI2019]唱、跳、rap和篮球】](https://www.luogu.com.cn/blog/command-block/solution-p5339) - [P5400 [CTS2019]随机立方体](https://www.luogu.com.cn/problem/P5400) [题解 P5400 【[CTS2019]随机立方体】](https://www.luogu.com.cn/blog/command-block/solution-p5400) - [[数学记录]P5401 [CTS2019]珍珠](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-p5401-cts2019-zhen-zhu) # 3.莫比乌斯反演 这一类反演关系非常特殊，可以用迪利克雷卷积来描述。 [莫比乌斯反演与数论函数](https://www.luogu.com.cn/blog/command-block/mu-bi-wu-si-fan-yan-ji-ji-ying-yong) # 4.Min-Max反演(容斥) [Min-Max容斥小记](https://www.luogu.com.cn/blog/command-block/min-max-rong-chi-xiao-ji) # 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 ](https://vjudge.net/problem/TopCoder-13444)。 **题意** : 给出一个 $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)$$ [评测记录](https://vjudge.net/solution/29090670) 咕了。找不到题做。 # 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] 数树](https://www.luogu.com.cn/problem/P5206) # 7.单位根反演 [单位根反演小记](https://www.luogu.com.cn/blog/command-block/dan-wei-gen-fan-yan-xiao-ji)