更新于 2026/7/8 08:18:12 作者

command_block

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

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

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

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

1.基本反演推论

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

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

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

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

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

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

也就是说，F=G∗AF=G*A。

已知 GG 求算 FF 是可行的。现在我们要由 FF 求算 GG。

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

比如，上面的前缀和的关系矩阵即为 A[n,i]=[i≤n]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]={−1(i=n−1)1(i=n)B[n,i]=\begin{cases}-1&(i=n-1)\\1&(i=n)\end{cases}

即 G[n]=∑i=0∞B[n,i]F[i]=F[n]−F[n−1]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=IA*B=I ，即矩互逆。

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

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

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

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

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

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

    • −1-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)^{m-n} ，然后分成两部分即可。

      可以使得只有一边有 −1-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)$

即任意的两个反演关系。

根据上问我们知道矩阵 (A1,B1),(A2,B2)(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[(n1,n2),(i1,i2)]=A1[n1,i1]A2[n2,i2]A[(n_1,n_2),(i_1,i_2)]=A_1[n_1,i_1]A_2[n_2,i_2] ，BB 类似。

欲证 A∗B=IA*B=I ，即证 (A∗B)[(n1,n2),(m1,m2)]=[(n1,n2)=(m1,m2)](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]$

=[n1=m1][n2=m2]=RHS=[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(ni)A[n,i]=(-1)^i\dbinom{n}{i} 这个矩阵是自逆的。

  • (经典代数)证明:\color{blue}\text{证明:} (A∗A)[d,t]=∑i=1∞A[d,i]A[i,t](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)!}$

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

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

      注意到 i−t=(d−t)−(d−i)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}$

    平移使得下界为 00 ( 把每个 ii 减去 tt ) 得到

    $\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(1-1)^{d-t}

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

    于是 A∗A=IA*A=I ，反演成立。

使用基本反演推论移动 −1-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 ，而这个东西左边是没有 −1-1 的。

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

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

    F[n]=∑i=0n(ni)G[i]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!}$

    辨识出卷积形式，以及 ex=∑i=0xii!e^x=\sum\limits_{i=0}\dfrac{x^i}{i!}

    F∗ex=G⟺G=F∗e−xF*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,GF,G 都是 00，所以不用在意上界问题。

移动 −1-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 信封问题

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

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

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

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

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

所以 n!=∑i=0n(ni)D[i]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]=∑i=0n(−1)ii!S[n]=\sum\limits_{i=0}^n\dfrac{(-1)^i}{i!} ,就能 O(n)O(n) 求解 D[1...n]D[1...n] 了。

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

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

我们称满足 Pi=iP_i=i 的 ii 为“不动点”。

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

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

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

则有 f(n,k)=∑m=k(mk)g(n,m)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)f(n,k) 则简单得多，因为其对未钦定的部分没有任何限制。

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

则有 f(n,k)=(nk)(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=0m=0 时二项式反演退化为经典容斥）

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

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

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

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

题目 : P4491 [HAOI2018]染色

题解 P4491 【[HAOI2018]染色】

  • 形式④④ :

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

    题意 : 有一棵 2m2m 个点的有根树，其中有 mm 个黑点, mm 个白点。

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

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

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

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

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

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

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

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

令 vv 为 uu 的直接儿子。

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

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

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

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

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

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

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

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

有 (ik)\dbinom{i}{k} 种方案从 ii 个好事件中钦定 kk 个，则有。

F[k]=∑i=kn(ik)G[i]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(n2)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×mn×m 的矩阵，每个位置可以填上 [1,c][1,c] 中的任意整数。

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

    n,m≤4000n,m\leq 4000.

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

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

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

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

能得到 :

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

组合意义 : 枚举 mm 列分成了 ii 个互不等价的集合，再将这 mm 列分配到这些集合中去。

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

使用斯特林反演可得 :

$$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⁡\gcd 就相当于取交集,注意到 [d∣(x,y)]=[d∣x][d∣y][d|(x,y)]=[d|x][d|y].

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

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

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

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

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

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

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

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

      f(S)=∑S⊆U[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⊆S−UT\subseteq S-U 类似于 t∣sut|\frac{s}{u} ,那么交换和式之后就有

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

      =∑T⊆U(−1)∣T∣F(S−T)=\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)$$

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

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

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

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

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

    类似地有F(U)=∑S⊆U∑P⊆Sμ(∣S−P∣)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)(1) 配合用于拆交集。和莫反中拆 gcd\rm gcd 是一个道理。

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

7.单位根反演

单位根反演小记

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 19ms
  4. Powered by Hydro v5.0.1 Community