计数理论杂谈 I：线性变换，各种卷积，反演

jiazhichen844 · 2025-04-04 19:16:48 · 个人记录

作为计数理论杂谈的第一篇文章，我决定明确一下计数领域的一些（较为容易的）技能点，于是我就准备讲一讲卷积（FFT，FWT）与反演，为了使更为容易的对卷积的复杂度优化有一个大体的认识，我们也会讲线性变换的概念。

你发现有很多技能点未在此文章提及，例如插值，生成函数，杨表等，如果有机会的话，之后总会讲的。

注：若无特殊说明，本文的数列都是 0-index 的。

Chapter 1.线性变换

定义

考虑一个函数 f(a)，其参数是一个长为 n 的数列，返回值是一个长为 m 的数列，f 可以被当成数列到数列的变换。
若存在 n\times m 的矩阵 e_{i,j}，满足 f(a)_i=\sum\limits_{j=0}^{n-1}a_je_{i,j}，则 f 被称为线性变换。
容易发现，若把一个数组看成向量，一个线性变换就是将其乘一个矩阵。（众所周知，线性代数第一颗基本都会讲矩阵）
线性变换的“线性”体现在哪？定义数列 a 乘数字 x 等价于将 a 中每一个数乘 x，两个等长数列相加为对位相加，对于线性变换 f，则有 f(xa+yb)=xf(a)+yf(b)，显然可以用矩阵的相关性质证明。

一个线性变换 f(a)，总可以被拆成 g_k(g_{k-1}(\cdots(g_1(g_0(a))))) 的形式，满足 g_x(a) 只有两种可能：一是删除或插入某一位，二是 a_x:=a_x+ka_y。
构造可以先对 f 对应的矩阵补成方阵，然后高斯消元，对消元后的上三角矩阵从后往前构造，再构造高斯消元的逆过程。

常见的线性变换

1.删除某一位/插入某一位
对应的矩阵为单位矩阵删去若干列插入若干列。

2.a_x:=a_x+ka_y
单位矩阵，然后 e_{x,y}:=e_{x,y}+k。

3.数列前缀和
对应的矩阵 e_{i,j} 应满足 e_{i,j}=1 当且仅当 i\le j，即这是一个上三角都为 1 的矩阵。

4.数列差分
对应的矩阵 e_{i,j} 满足主对角线都是 1，且 e_{i-1,i}=-1。

差分具有线性性质的根本原因就是其实一个线性变换。

几何意义

根据上面的性质，如果我们把一个数列看成 n 维空间上的一个点，一个线性变换会执行若干步，每步只有三种可能：一是在某一维的水平面上投影，二是新加一维，不改变原有点坐标，三是选择某一维，将这一维的坐标轴任意摆放（不需要垂直），任意缩放，重构坐标系上的点（保持坐标不变），复原坐标轴（保持点的位置不变）。
如果这个线性变换满足前后数组长度不变，则对应到空间里就是将空间坐标轴任意摆放缩放，再把点重构，再把坐标轴重构。

线性变换的逆

线性变换 f(a) 的逆 g(a) 满足 f(g(a))=g(f(a))=a，所以若 f(a) 和 g(a) 互为逆，则 g 的返回值的长度等于 f 的参数的长度，f 的返回值的长度等于 g 的参数的长度。
一个线性变换有逆，当且仅当把它拆分成上文所述的形式时，任意的 g_i(a) 都不会是删除、插入某一位或 a_x:=a_x+(-a_x)。
一个线性变换逆的构造可以根据拆分方式构造，同时也可以构造其矩阵对应的逆矩阵。

Chapter 2.卷积

定义

对于数列 a,b，定义他们的卷积 c_k=\sum\limits_{i\ \text{op}\ j=k}a_ib_j，其中 \text{op} 为一种运算。
不难发现，若 a,b 长度都为 n，计算卷积的时间复杂度为 O(n^2)。
下文中，我们将会从易到难讲解如何优化卷积。
以下设 c_i 只用保留前 n 项。

基本思路

一些学过 FFT，FWT 的人很容易想出这一点，优化卷积的基本思路就是构造一个线性变换 f，满足 f(a\times b)=f(a)\cdot f(b)，其中 (a\cdot b)_i=a_ib_i，此时只要这个线性变换的性质足够良好就能做到更低的复杂度。

狄利克雷卷积

当我们取 \text{op}=\times，即 c_i=\sum\limits_{jk=i}a_jb_k 时，我们称其为狄利克雷卷积（Dirichlet convolution）。
一般，狄利克雷卷积的数列是 1-index 的。
容易发现，当我们先枚举 j，再枚举 k\le \frac nj，此时复杂度为 O(\sum\limits_{i=1}^n \frac ni)=O(n\log n)，不必优化。
当 b_i=1 时，c_i=\sum\limits_{j|i}a_j，令 f(a)=c，则 f 被称为狄利克雷前缀和。
狄利克雷前缀和的逆我们将在第三章讲解。

和卷积

当我们取 \text{op}=+，即 c_i=\sum\limits_{j=0}^i a_jb_{i-j} 时，c 被称作 a 和 b 的和卷积。
考虑构造线性变换的矩阵 e。
我们应满足 f(c)_i=f(a)_if(b)_i，即 \sum\limits_{j=0}^{n-1} c_je_{j,i}=(\sum\limits_{j=0}^{n-1}a_je_{j,i})(\sum\limits_{j=0}^{n-1}b_je_{j,i})。
代入 c_i=\sum\limits_{j=0}^i a_jb_{i-j}，得 \sum\limits_{j=0}^{n-1} \sum\limits_{k=0}^j a_kb_{j-k}e_{j,i}=\sum\limits_{j=0}^{n-1}\sum\limits_{k=0}^{n-1}a_jb_ke_{j,i}e_{k,i}。
比较 a_jb_k 的系数，得 e_{j+k,i}=e_{j,i}e_{k,i}。
显然（？），若 a_i\neq 0,\forall i\neq j,a_i\neq a_j 则 e_{i,j}=(a_j)^i 是合法的。
若取 a_j=j+1，则这个线性变换还是只能 O(n^2) 求。
令 n\le m=2^k，注意到取 a_j=\omega_m^j 是合法的。\omega_k 是 k 次单位根。
此时，注意到，e 的左右两边很像，e_{i,j+\frac m2}=(-1)^ie_{i,j}。
这启发我们将行按奇偶拆开，将列按左右拆开，此时只用管左边的列。
按行拆后形如 \sum\limits_{j=0}^{\frac m2-1} b_j\omega_m^{i(2j+1)}=\omega_m^i\sum\limits_{j=0}^{\frac m2-1}b_j\omega_m^{2ij}=\omega_m^i\sum\limits_{j=0}^{\frac m2-1}b_j\omega_{\frac m2}^{ij}。
发现这个等价于原问题，分治即可。
时间复杂度 O(n\log n)。
哦不对，我还要求这个矩阵的逆。
众所周知，满足 e_{i,j}=(a_j)^i 的矩阵叫范德蒙德矩阵。
然后我们取的这个范德蒙德矩阵非常特殊，其逆矩阵为原矩阵每个数取倒数再除以 m。
然后这个逆矩阵显然也是范德蒙德矩阵，也有左右相反的性质，所以可以再做一遍。
这个线性变换 f 叫 DFT（Discrete Fourier Transform），其逆变换 f^{-1} 叫 IDFT（Inverse Discrete Fourier Transform）。
这样你就会 FFT（Fast Fourier Transform） 啦！
哦还有， \omega_k 显然是一个复数，但当 k\mid mod-1 时，取 \omega_k=g^{\frac{mod-1}{k}} 性质良好。
这样你就会 NTT（Number-Theoretic Transform） 啦！
例题：P3803。

差卷积

取 \text{op}=-，即 c_i=\sum\limits_{j=0}^{n-1} a_{j+i}b_{j} 时，c 被称作 a 和 b 的差卷积。
容易发现，若我们令 b'_i=b_{n-1-i}，则 c_i=\sum\limits_{j=0}^{n-1} a_{j+i}b'_{n-1-j}，为 a 与 b' 和卷积 a\times b' 的第 n+i-1 项。
时间复杂度 O(n\log n)。
例题：P3338。

与卷积

取 \text{op}=\And，即 c_i=\sum\limits_{j\And k=i}a_jb_k 时，我们称 c 为 a 和 b 的与卷积。
类似和卷积的推导过程，我们构造的 e 应满足 e_{j\And k,i}=e_{j,i}e_{k,i}。
我们构造 e_{i,j}=[j\subseteq i]=[i\And j=j]，容易发现符合性质。
问题变成了求 b_j=\sum\limits_{j\subseteq i} a_i，即超集和。
高维后缀和即可，时间复杂度 O(n\log n)。

或卷积

取 \text{op}=|，即 c_i=\sum\limits_{j|k=i}a_jb_k 时，我们称 c 为 a 和 b 的或卷积。
显然，我们构造的 e 应满足 e_{j|k,i}=e_{j,i}e_{k,i}。
构造 e_{i,j}=[i\subseteq j]=[i\And j=i]。
问题变成了求 b_j=\sum\limits_{i\subseteq j} a_i，即子集和。
高维前缀和即可，时间复杂度 O(n\log n)。
逆变换显然。

异或卷积

取 \text{op}=\oplus，即 c_i=\sum\limits_{j\oplus k=i} a_jb_k。
同理，我们构造的 e 应满足 e_{j\oplus k,i}=e_{j,i}e_{k,i}。
这个构造怎么推的我仔细讲一下。
注意到 e_{i,x}=(-1)^{popcnt(i)} 是一种合法的列，因为有 popcnt(x\oplus y)\equiv popcnt(x)+popcnt(y)\pmod 2
发现 popcnt((x\oplus y)\And k)=popcnt((x\And k)\oplus(y\And k))\equiv popcnt(x\And k)+popcnt(y\And k)\pmod 2。
所以我们可以构造 e_{i,j}=(-1)^{popcnt(i\And j)}。
我们现在要求 b_j=\sum\limits_{i=0}^{n-1} (-1)^{popcnt(i\And j)} a_i。
设 n=2^k，考虑分治。
先将前 2^{k-1} 个数和后 2^{k-1} 个数分别变换为对应的 b，然后考虑他们之间的贡献。
对于 a_i 和 a_{i+2^{k-1}}，我们让 a_i:=a_i+a_{i+2^{k-1}},a_{i+2^{k-1}}:=a_i-a_{i+2^{k-1}}，原因显然。
对于逆变换，同理，自行推导。
这个东西和高维前缀和放一块，叫 FWT。
时间复杂度 O(n\log n)。
例题：P4717，P6097。

Chapter 3.反演

定义

反演，可以认为是反向演化，即对于一些常用的线性变换构造逆的过程。
通常这些过程需要伴随着加减，所以作者在介绍反演套路时会带上一些容斥套路（或者说反演和容斥本身就难以分清）。
Limie 表示反演是容斥的高级叫法及扩展，作者认为反演是容斥的理性说明。

差分

对于两长度为 n 的数组 f,g，有以下两个结论：

• f_i=\sum\limits_{j=0}^i g_j\Leftrightarrow g_i=f_i-f_{i-1}
• f_i=\sum\limits_{j=i}^{n-1} g_j\Leftrightarrow g_i=f_i-f_{i+1}

证明是显然的。
差分一般用于解决“最值恰好为 n 的方案数”的问题（这需要和 min-max 反演区分），以最大值为例，我们定义 g_i 为“最小值恰好为 i”的方案数，f_i=\sum\limits_{j=i}^{n-1} g_j，则 f_i 为“所有元素都 \ge i”的方案数（\ge i 需要和二项式反演中的“钦定……一定”区分）。
有的时候，f 反而是好求的（更为独立），此时只需求 f_i,f_{i+1} 两个单点的值即可求出 g_i。

子集反演

对于两个定义域为 \{0,1,\cdots,n-1\} 的，值域为数字的函数 f,g，有以下两结论：

• f(S)=\sum\limits_{T\subseteq S}g(T)\Leftrightarrow g(S)=\sum\limits_{T\subseteq S} (-1)^{|S|-|T|} f(T)
• f(S)=\sum\limits_{S\subseteq T}g(T)\Leftrightarrow g(S)=\sum\limits_{S\subseteq T} (-1)^{|T|-|S|} g(T)

第一个结论证明：
注意到 g\to f 是一个线性变换，所以只需证明结论是正确的，根据逆的唯一性就可得出无其他式子。
起手代入，只需证 f(S)=\sum\limits_{T\subseteq S}\sum\limits_{T'\subseteq T} (-1)^{|T|-|T'|}f(T')。

• f_i=\sum\limits_{j=i}^{n-1} \binom jig_j\Leftrightarrow g_i=\sum\limits_{j=i}^{n-1} (-1)^{j-i} \binom jif_j

证明形似于子集反演，读者自证不难，给两个式子：

1. \binom ab\binom bc=\binom ac\binom{a-c}{b-c}
2. \sum\limits_{i=0}^n \binom ni x^iy^{n-i}=(x+y)^n

虽然但是，若子集反演中 f(S) 只于 |S| 有关，即可写为二项式反演。

二项式反演最重要的在于其用法，重点在于第二个式子：

使用二项式反演的题一般都是给若干限制，要求满足限制数 恰好 为 x，令 g_i 为 恰好 满足 i 个条件的方案数，f_i 为 钦定 i 个条件一定满足的方案数，则 f,g 满足上二式。

lengendcn：啊什么？钦定 和 大于等于 不是一样的吗，所以这个不是应该套差分的式子吗？
这是非常容易混淆的一点，钦定 i 个的意思是，我选择 i 个条件，让他们一定合法，对于所有选择 i 个条件的方案，将合法的方案数相加，得到的总和就是 钦定 i 个合法的方案数。
换句话说，钦定 是有一个选择和故意算重的过程的。
但这个故意算重的过程使 钦定…… 变得更为好算，因为只需 选择 i 个条件合法即可，不用管没被选到的条件，选择的过程大多容易使用 dp 计算。
设实际上有 j 个条件合法，我们 钦定 i 个合法，则这 j 个条件中任意选 i 个的方案的可能都会被计算一次，一共会被计算 \binom ji 次，但 大于等于 只会被计算 1 次，所以 f,g 符合上二式。

使用二项式反演，只需求出 f 就能求 g 的单点，此时也可以尝试将容斥系数丢进 dp。
什么？你想求所有 g，但是只会 O(n^2)？
将组合数展开，有 g_i=(-1)^ii!\sum\limits_{j=i}^{n} \frac{(-1)^jf_j}{j!}\frac{1}{(j-i)!}，差卷积即可，时间复杂度 O(n\log n)。

求求你们不要在题解里把 钦定 写成 大于等于 了！！！就这个问题在 2024 年 3 月让我想了两天。

例题：P4859，P4491。

以上三种反演是最经典的（提高组考了可以解释为“容斥基础”）的容斥方法，其中差分与二项式反演较为容易混淆，当遇到“恰好”等字眼时，应优先考虑二项式反演，当遇到“最值”等字眼时，应优先考虑差分。

莫比乌斯反演

莫比乌斯反演 是 狄利克雷前缀和 的逆，也是把 差分 丢上质因数指数的形式。
一句话描述：\mu*I=\epsilon。（* 是狄利克雷卷积）
又一句话描述：g=f*I \Leftrightarrow f=g*\mu。
人话描述：对于两长度为 n 的 1-index 的数组 f,g，有以下两个结论：

• f_i=\sum\limits_{j|i} g_j\Leftrightarrow g_i=\sum\limits_{j|i}f_j\mu(\frac ij)
• f_i=\sum\limits_{i|j} g_j\Leftrightarrow g_i=\sum\limits_{i|j}f_j\mu(\frac ji)

什么？你告诉我你不知道什么是 \mu(x)？

若 \exist d>1 使 d^2\mid x，则 \mu(x)=0。
否则设 x=\prod\limits_{i=1}^k p_i，则 \mu(x)=(-1)^k。

证明：
若 \mu*I=\epsilon,g=f*I，则 g*\mu=f*I*\mu，则 g*\mu=f，所以只需证 \mu*I=\epsilon。
相当于证 \sum\limits_{d|n}\mu(d)=[n=1]。
设 n=\prod\limits_{i=1}^k p_i^{\alpha_i}。
因为若 \exist d^2\mid n 则 \mu(n)=0。
所以若设 d=\prod\limits_{i=1}^k p_i^{\beta_i}，则 \beta_i\in\{0,1\}，贡献为 (-1)^{\sum\beta_i}。
枚举 \beta_i 为 1 的 i 的集合，则为 \sum\limits_{S\subseteq\{1,2,\cdots,k\}} (-1)^{|S|}。
注意到非空集合的奇子集与偶子集构成双射，所以上式 =[k=0]。

枚举 t=gd，答案为 \sum\limits_{t=1}^n (\sum\limits_{g|t}f(g)\mu(\frac tg))(\sum\limits_{i=1}^{\lfloor\frac nt\rfloor}h(it))(\sum\limits_{i=1}^{\lfloor\frac mt\rfloor}h(it))。
第一个括号预处理，后面两个推式子，然后数论分块即可。
例题：AGC038C。

单位根反演

结论：[n\mid k]=\frac 1n\sum\limits_{i=0}^{n-1} \omega_{n}^{ik}。

证明：
当 n\mid k 时，\omega_n^k=1，\frac{1}{n}\sum\limits_{i=0}^{n-1}1^i=1。
否则，\omega_n^k\neq 1,\frac{1}{n}\sum\limits_{i=0}^{n-1}\omega_n^{ik}=\frac{1-\omega_n^{nk}}{n(1-\omega_n^k)}=\frac{0}{n(1-\omega_n^k)}=0。

用法很显然，就是把 [n\mid k] 代入成 \frac 1n\sum\limits_{i=0}^{n-1} \omega_{n}^{ik}，然后交换求和顺序即可。
对于一些和 i\mod k 有关的东西，先枚举他 =x，则有 k\mid i-x，展开成为 \frac 1k\sum\limits_{j=0}^{k-1}\omega_k^{j(i-x)}，然后通过一些手段解决问题。

min-max 反演

结论：

证明可以归纳。

从式子上可以看出，他主要是求期望最大值的问题。

对于多物体随机过程的期望停时问题，令物体 i 的结束时间为 t_i，则要求 E(\max(t))，可尝试通过 min-max 反演式转化，常与容斥 dp 结合。

以上是一些常用的反演过程，实战中较为常用。

本文大抵到此为止，此为作者学习计数时一篇小记，望对大家产生帮助。

再来一篇：不是，你们都是怎么拥有这么逆天的想法的（计数理论杂谈 II：【数据删除】）。