生成函数讲稿

发表于 2023-12-05 分类于知识点阅读次数： Waline：

长文预警！

矩阵、行列式与矩阵树定理

参考

简单线性代数前置知识

矩阵
- 矩阵的定义：数表
  - \(n\) 阶矩阵
  - 全 0 矩阵：\(O\)
  - \(n\) 维行向量、\(n\) 维列向量
  - 主对角线、副对角线
  - 上三角矩阵、下三角矩阵、对角矩阵
    - 数量矩阵（对角线全相同的对角矩阵）
    - 单位矩阵（对角线为 \(1\) 的数量矩阵，一般记作 \(E\)）
- 矩阵加法、数乘、乘法
  - 乘法满足结合律
- 矩阵的转置
  - \((A^T)^T=A\)
  - \((A+B)^T=A^T+B^T\)
  - \((AB)^T=B^TA^T\)
  - \((kA)^T=kA^T\)
- 分块矩阵
  - 定义
  - 加减法、数乘
  - 乘法
  - 转置
  - 分块对角矩阵
- 行/列初等变换
  - 内容
    - 交换两行/列
    - 将一行/列 \(\times k\)
    - 将一行/列 \(\times k\) 并加到另一行/列上
  - 都是可逆的
  - 行/列阶梯形矩阵、行/列最简形矩阵
  - 标准型矩阵
  - Bonus: 自行了解齐次线性方程组与行/列最简形矩阵的关系
  - 初等矩阵（P25）
    - 初等矩阵的逆
    - 行初等变换相当于左乘初等矩阵，列初等变换相当于右乘初等矩阵
  - 行等价、列等价与等价
- 逆矩阵
  - 定义：对于 \(A\)，如果存在 \(AB=BA=E\)，那么称 \(B\) 是 \(A\) 的逆矩阵，记作 \(A^{-1}\)
  - 性质
    - 若 \(A\) 可逆，则 \(A^{-1}\) 可逆，且 \((A^{-1})^{-1}=A\)
    - 若 \(A_1,A_2,\cdots A_k\) 都可逆，则 \(A_1A_2\cdots A_k\) 也可逆，且 \((A_1A_2\cdots A+k)^{-1} = A_k^{-1} A_{k-1}^{-1} \cdots A_1^{-1}\)
    - 若 \(A\) 可逆，则 \(A^T\) 也可逆，且 \((A^T)^{-1}=(A^{-1})^T\)
    - 若 \(A\) 可逆且 \(k\ne 0\)，则 \(kA\) 可逆，且 \((kA)^{-1} = k^{-1}A^{-1}\)
  - （逆矩阵与初等变换的关系）下面三个命题互相等价：（P27）
    - \(n\) 阶矩阵 \(A\) 可逆
    - \(n\) 阶矩阵 \(A\) 行（列）等价于 \(E\)
    - 矩阵 \(A\) 可表示为若干初等矩阵的乘积
行列式
- \(n\) 阶行列式的定义
  - \(|A|=\det A=\sum_{\{p_i\}\in P}(-1)^{\tau(p)}a_{1p_1}a_{2p_2}\cdots a_{np_n}\)
- 性质
  - 上三角矩阵、下三角矩阵和对角矩阵的行列式都等于对角线元素之积
  - \(|A| = |A^T|\)
  - 互换行列式的两行/列，行列式变号
  - 如果行列式的两行/列相等，则行列式为 \(0\)
  - 行列式的数乘（将某行/列乘上 \(k\)，行列式的值也乘上 \(k\)）
  - \(|kA| = k^n|A|\)
  - 如果行列式的某行/列全为 \(0\)，则行列式为 \(0\)
  - 如果行列式的某两行/列对应成比例，则行列式为 \(0\)
  - 行列式的拆分定理（P43）
  - 把行列式的某行（列）\(\times k\) 加到另外一行（列），行列式不变
- 行列式可逆的充要条件是 \(|A|\ne 0\)
- \(|AB| = |A|\cdot |B|\)（P49）
余子式、代数余子式（选学，不想听证明可以不管）
- 定义
  - 余子式：\(M_{ij}\)，表示将矩阵 \(A\) 的第 \(i\) 行和第 \(j\) 列去掉得到的矩阵的行列式
  - 代数余子式：\(A_{ij}=(-1)^{i+j}M_{ij}\)
- 矩阵按行、列展开（拉普拉斯展开）（P53）
  - \(\forall 1\le i\le n, |A|=\sum_{k=1}^n a_{ik} A_{ik}\)
  - \(\forall 1\le j\le n, |B|=\sum_{k=1}^n a_{kj} A_{kj}\)
  - 推论：\(\forall i\ne j, a_{i1}A_{j1}+a_{i2}A_{j2}+\cdots a_{in}A_{jn}=0\)（P56）
  - 推论：\(\forall i\ne j, a_{1i}A_{1j}+a_{2i}A_{2j}+\cdots a_{ni}A_{nj}=0\)（P56）

矩阵树定理

Binet-Cauchy 定理
基尔霍夫矩阵
引理
证明

Bonus: Cayley 公式

习题

P3317 [SDOI2014] 重建
 Stranger Trees
P4336 [SHOI2016] 黑暗前的幻想乡

普通生成函数 OGF

参考

引入

定义
- ordinary generating function
- 数乘、卷积定义
求 Fibonacci

简单运算

首先有一个经典的生成函数：

\(\langle 1, 1, 1, \cdots \rangle {\overset{\mathbf{OGF}}{\longrightarrow}} \dfrac{1}{1 - x}\)

然后有一些变换：

平移
- \(\langle a_0, a_1, a_2, \cdots \rangle \longrightarrow \langle \underbrace{0, 0, \cdots, 0}_{c\ 个}, a_0, a_1, a_2, \cdots \rangle\)
- \(F(x) \to x^c F(x)\)
拉伸
- \(\langle a_0, a_1, a_2, \cdots \rangle \longrightarrow \langle a_0, \underbrace{0, 0, \cdots, 0}_{c - 1\ 个}, a_1, \underbrace{0, 0, \cdots, 0}_{c - 1\ 个}, \cdots \rangle\)
- \(F(x) \to F(x^c)\)
扩倍（数乘）
- \(\langle a_0, a_1, a_2, \cdots \rangle \longrightarrow \langle ka_0, ka_1, ka_2, \cdots \rangle\)
- \(F(x) \to kF(x)\)
乘等比数列
- \(\langle a_0, a_1, a_2, \cdots \rangle \longrightarrow \langle a_0c^0, a_1c^1, a_2c^2, \cdots \rangle\)
- \(F(x) \to F(cx)\)
求导
- \(\langle a_0, a_1, a_2, \cdots \rangle \longrightarrow \langle a_1, 2a_2, 3a_3, \cdots \rangle\)
- \(F(x) \to F'(x)\)
- 更进一步的：
  - \(\langle a_0, a_1, a_2, \cdots \rangle \longrightarrow \langle c^{\underline{c}}\times a_c, (c+1)^{\underline{c}}\times a_{c + 1}, (c+2)^{\underline{c}}\times a_{c + 2}, \cdots \rangle = \sum\limits_{i=c}i^{\underline{c}}a_i x^{i-c}\)

另外还有一些更加困难一点的东西：

（前置：二项式定理，广义二项式定理，经典微积分）

\(\sum\limits_{i=0}\dbinom{n}{i}x^i = (x+1)^n\)
\(\sum\limits_{i=0}(-1)^i\dbinom{n}{i}x^i = (1-x)^n\)
\(\sum\limits_{i=0}\dbinom{n+i}{i}x^i = \dfrac{1}{(1-x)^{n+1}}\)
\(\sum\limits_{i=1}\dfrac{x^i}{i} = -\ln (1-x)\)

例题

\(a_n = 8a_{n-1} + 10^{n - 1}\)，\(a_1=9\)，求 \(a\) 的通项公式。
生成函数推 Catalan 数 \(h_n (0\le n\le n)\)：

\[ h_n = \begin{cases} \sum_{i=0}^{n-1} h_i h_{n-i-1} &(n\ge 2)\\ 1 &(n\in [0, 1]) \end{cases} \]

请尝试用生成函数方法证明下面两个问题的答案相等：（Bonus: 其实这个可以建立双射，~~留作思考题~~）
- 把 \(n\) 分为若干份，每份为正奇数的方案数
- 把 \(n\) 分为若干个不同正整数之和的方案数
CF1821F Timber
- 比较入门的题

习题

P3978 [TJOI2015] 概率论
 BZOJ 2173 「国家集训队」整数的lqp拆分
 BZOJ 3027 [CEOI2004]Sweet

拓展

自行了解：

计算 \(\sum\limits_{k\ge 0}\dbinom{k}{n-k}\) 的封闭形式。（Snake Oil Trick，解法直接翻到 Snake Oil Trick 那里）
五边形数定理

指数生成函数

参考

引入

定义
- exponential generating function
- 数乘、卷积定义

简单运算

\(\langle 1, 1, 1, \cdots \rangle {\overset{\mathbf{EGF}}{\longrightarrow}} e^x\)
- 泰勒展开
\(\langle 1, -1, 1, -1, 1, \cdots \rangle {\overset{\mathbf{EGF}}{\longrightarrow}} e^{-x}\)
\(\langle c^0, c^1, c^2, \cdots \rangle {\overset{\mathbf{EGF}}{\longrightarrow}} e^{cx}\)
\(\langle 1, 0, 1, 0, 1, 0, \cdots \rangle {\overset{\mathbf{EGF}}{\longrightarrow}} \dfrac{e^x+e^{-x}}{2}\)
\(\langle 1, \alpha, \alpha^{\underline{1}}, \alpha^{\underline{2}}, \alpha^{\underline{3}}, \cdots \rangle {\overset{\mathbf{EGF}}{\longrightarrow}} (1 + x)^\alpha\)
- \(\alpha\) 可以为实数
- 广义二项式定理

“组合对象的拼接”——卷积，ln, exp 与 EGF

EGF 卷积——组合对象的“归并”
- OGF: {AAA}×{BBB}={AAABBB}（集合的合并）
- EGF: (AAA)×(BBB)={(AAABBB),(AABBAB),(ABBAAB),(BBAAAB),……}共 \(\binom{3+4}{3}\) 种（序列的归并）
对 EGF 进行 \(\exp\)——组合对象的“生成集合”
- \(\exp F(x) = \sum\limits_{i=0}\dfrac{F^i(x)}{i!}\)
- 将 \(F(x)\) 看成一个“元素”，对若干个“元素”的有标号集合计数
  - 有标号集合的“元素”之间无序（因为除以了阶乘），“元素”内部的东西是 有编号 的（因为需要归并）
  - 如果长度为 \(n\) 的置换环个数为 \(f(n)\)，设其 EGF 为 \(F(x)\)，则长度为 \(n\) 的置换环集合（即长度为 \(n\) 的排列）的个数为 \([\frac{x^n}{n!}]\exp F(x)\)
  - 如果 有标号 生成树的 EGF 为 \(F(x)\)，则 有标号 森林的 EGF 为 \(\exp F(x)\)

例题

求第一、二类斯特林数的一列。（需要多项式快速幂）
有标号连通无向图计数
- 设有标号简单无向图的 EGF 为 \(F(x) = \sum\limits_{i=0} \dfrac{2^{i(i-1)/2}}{i!}x^i\)，则答案为 \(\ln F(x)\)。
P7364 有标号二分图计数
- 考虑一张连通二分图的黑白染色方案为 \(2\)
- 我们只需要枚举黑点集合然后连边，就能得出任意二分图染色数
- 然后 \(\ln\) 就是连通二分图染色数
- 然后除以 \(2\) 就能算出连通二分图个数
- 最后再 \(\exp\) 回去就是任意二分图个数了
- 发现设任意二分图染色方案的 EGF 为 \(F(x)\)，那么答案是 \(\exp(\frac 12 \ln F(x))\)，容易发现这就等于 \(\sqrt{F(x)}\)，可以减小代码长度和常数。
ABC231G Balls in Boxes

习题

POJ3734 Blocks（无需 FFT/NTT）
POJ1322 Chocolate（无需 FFT/NTT）
P4389 付公主的背包（需要 FFT/NTT）

多项式全家桶

参考

题外话：我有一份封装模板，需要的可以找我要，~~我感觉跑得还是挺快的~~。

FFT 与 NTT

移步我的博客。

Bonus: DIF 与 DIT，可以参考这个。

例题： 求第二类斯特林数的一行。

牛顿迭代法

对于函数 \(F(x)\)，如果有 \(G(F(x)) = 0\)，并且我们已经求出 \(G(F_*(x)) \equiv 0 \pmod{x^{\frac n2}}\)，那么我们就可以通过牛顿迭代求出 \(F \bmod x^n\)：

\[ F(x) \equiv F_*(x) - \frac{G(F_*(x))}{G'(F_*(x))} \pmod{x^{n}} \]

注意这里的 \(G'(F_*(x))\) 是以 \(F(x)\) 为主元的，即 \(\dfrac{\operatorname{d} G(F_*(x))}{\operatorname{d} F_*(x)}\)。

一个需要注意的地方是 \(\dfrac{1}{G'(F_*(x))}\) 的精度只需要达到 \(x^{\frac n2}\)，因为 \(G(F_*(x))\) 的前 \(\frac n2\) 项必然为 \(0\)（定义）。

证明：

首先显然有 \(F(x) \equiv F_*(x) \pmod{x^{\frac n2}}\)。我们把 \(G(F(x))\) 在 \(F_*(x)\) 处泰勒展开：

\[ G(F(x)) = G(F_*(x)) + \frac{G'(F_*(x))}{1!}(F(x) - F_*(x)) + \frac{G''(F_*(x))}{2!}(F(x) - F_*(x))^2 + \cdots \]

看起来这个式子更加复杂了，但是我们发现 \(F(x)\) 和 \(F_*(x)\) 的前 \(\frac n2\) 项都相同，所以 \(F(x) - F_*(x)\) 的后 \(\frac n2\) 项为 \(0\)，进而我们可以得到 \((F(x) - F_*(x))^c \bmod x^n = 0 (c\ge 2)\)。所以我们可以把上面的式子写为：

\[ \begin{aligned} G(F(x)) &\equiv G(F_*(x)) + G'(F_*(x))(F(x) - F_*(x)) &\pmod{x^n}\\ G'(F_*(x))F(x) &\equiv G(F(x)) - G(F_*(x)) + G'(F_*(x))F_*(x) &\pmod{x^n}\\ F(x) &\equiv \frac{G(F(x)) - G(F_*(x)) + G'(F_*(x))F_*(x)}{G'(F_*(x))} &\pmod{x^n}\\ &\equiv F_*(x) + \frac{G(F(x)) - G(F_*(x))}{G'(F_*(x))} &\pmod{x^n}\\ &\equiv F_*(x) - \frac{G(F_*(x))}{G'(F_*(x))} &\pmod{x^n} \end{aligned} \]

多项式求逆

下面讲的东西基本上都有两种推法，第一种是直接推，第二种是用牛顿迭代。下面只讲牛顿迭代的方法。

记 \(F(x)\) 的逆为 \(F^{-1}(x)\)，我们令 \(G(H(x)) = F(x)H(x) - 1\)，那么 \(G(F^{-1}(x))=0\)。套用牛顿迭代的公式：

\[ \begin{aligned} F^{-1}(x) &\equiv F^{-1}_*(x) - \frac{G(F^{-1}_*(x))}{G'(F^{-1}_*(x))} &\pmod{x^n}\\ &\equiv F^{-1}_*(x) - \frac{F(x)F^{-1}_*(x) - 1}{F(x)} &\pmod{x^n}\\ \end{aligned} \]

注意到 \(\dfrac{1}{F(x)}\) 的精度只需要 \(x^{\frac n2}\)，所以可以直接用 \(F^{-1}_*(x)\)。最终的式子是

\[ \begin{aligned} F^{-1}(x) &\equiv F^{-1}_*(x) - F^{-1}_*(x)(F(x)F^{-1}_*(x) - 1) &\pmod{x^n}\\ &\equiv F^{-1}_*(x)(2 - F(x)F^{-1}_*(x)) &\pmod{x^n}\\ \end{aligned} \]

直接倍增+NTT 计算即可。复杂度 \(T(n)=T(\frac n2) + O(n\log n) = O(n\log n)\)。

多项式开根

令 \(G(H(x)) = H^2(x) - F(x)\)，记 \(H(x) = \sqrt{F(x)}\)，则 \(G(H(x)) = 0\)。

\[ \begin{aligned} H(x) &\equiv H_*(x) - \frac{G(H_*(x))}{G'(H_*(x))} &\pmod{x^n}\\ &\equiv H_*(x) - \frac{H_*^2(x) - F(x)}{2H_*(x)} &\pmod{x^n}\\ &\equiv \frac{H_*^2(x)+F(x)}{2H_*(x)} &\pmod{x^n} \end{aligned} \]

直接做即可。

需要注意的是，\(\sqrt{F_0}\) 需要求二次剩余。不过一般来说，由于生成函数是有实际意义的，所以基本上都有 \(F_0=1\)，此时不需要二次剩余。（我的板子没写二次剩余，需要保证 \(F_0=1\)）

多项式取模

这个比较简单。

对于 \(n\) 次多项式 \(F(x)\) 和 \(m\) 次多项式 \(G(x)\)，求商（\(n - m\) 次）多项式 \(Q(x)\) 和余数（至多 \(m - 1\) 次）多项式 \(R(x)\)。注意这里不是模 \(x^n\) 意义下的，所以才会出现余数，和上面的多项式求逆不同。

不难得到 \(F(x) = Q(x)\times G(x) + R(x)\)。

考虑用取模把余数去掉。但是由于余数必然是较低项不好去除，所以我们把所有多项式“翻转”。

具体地，对于 \(n\) 次多项式 \(F\)，定义 \(F^T(x)=x^nF(x^{-1})\)，手玩发现 \(F^T(x)\) 就是将 \(F(x)\) 所有系数翻转得到的多项式。

\[ \begin{aligned} F(x) &= Q(x)G(x) + R(x)&\\ F(x^{-1}) &= Q(x^{-1})G(x^{-1}) + R(x^{-1})&\\ x^nF(x^{-1}) &= x^n Q(x^{-1})G(x^{-1}) + x^n R(x^{-1})&\\ F^T(x) &= Q^T(x) G^T(x) + x^{n - m + 1}R^T(x)&\\ F^T(x) &\equiv Q^T(x) G^T(x) &\pmod{x^{n - m + 1}}\\ Q^T(x) &\equiv \frac{F^T(x)}{G^T(x)} &\pmod{x^{n - m + 1}}\\ \end{aligned} \]

这样就可以用多项式求逆算出 \(Q(x)\)，然后容易算出 \(R(x)\)。

Bonus: 常系数齐次线性递推（可以参考这个）

多项式 ln

应该保证 \([x^0]F(x) = 1\)。

这个很简单：\((\ln F(x))' = \frac{F'(x)}{F(x)}\)，所以 \(\ln F(x) = \int \frac{F'(x)}{F(x)}\)

这里说一下 \(\ln\) 和 \(\exp\) 的定义：

\[ \ln F(x) = -\sum_{i=0}\frac{(1-F(x))^i}{i} \]

\[ \exp F(x) = \sum_{i=0}\frac{F(x)^i}{i!} \]

这个是麦克劳林级数的定义，这个定义只用到了加法和乘法，所以可以对 \(x^n\) 取模而不会出错。

经典的性质在这个定义下仍然成立，如 \(\exp\), \(\ln\) 互为逆运算，\(\exp(\ln F(x)+\ln G(x))=F(x)\times G(x)\) 等。

多项式 exp

应该保证 \([x^0]F(x) = 0\)。

由于 \(\exp\) 与 \(\ln\) 是逆运算，所以可以牛顿迭代：

令 \(G(H(x)) = \ln H(x) - F(x)\)，记 \(H(x) = \exp F(x)\)，则 \(G(H(x)) = 0\)。

\[ \begin{aligned} H(x) &\equiv H_*(x) - \frac{G(H_*(x))}{G'(H_*(x))} &\pmod{x^n}\\ &\equiv H_*(x) - \frac{\ln H_*(x) - F(x)}{H^{-1}_*(x)} &\pmod{x^n}\\ &\equiv H_*(x) - (\ln H_*(x) - F(x))H_*(x) &\pmod{x^n}\\ &\equiv H_*(x)(1 - \ln H_*(x) + F(x)) &\pmod{x^n}\\ \end{aligned} \]

但是这个做法既需要使用 \(\ln\)，而且常数还大，根本没有性价比。所以还有一个分治 NTT 的 \(O(n\log^2 n)\) 的做法：

设 \(G(x) = \exp F(x)\)，两边同时求导可得 \(G'(x)=G(x)F'(x)\)。

对两边同时提取 \(x^n\) 系数，则 \((n+1)G_{n+1}=\sum_{i=0}^n (i+1)F_{i+1}G_{n-i}\)，也就是 \(G_n = \frac 1n \sum_{i=1}^n iF_i G_{n-i}\)。然后就可以分治 NTT 了。

多项式快速幂

很简单。

\(F^k(x) \equiv \exp(k\times \ln F(x)) \pmod{x^n}\)

应用： 求第一、二类斯特林数的一列。

例题

模板题

P3338 [ZJOI2014] 力
- 直接做
Point Distance
- 考虑计算出横纵坐标距离分别为 \((x, y)\) 的点对个数，这是一个“二维差卷积”
- 差卷积可以通过翻转下标解决
- 二维的话可以用经典做法：令 \(g_{iT+j}=f_{i,j} (T>2n)\) 并对 \(g\) 做卷积，得到的序列再转回去就是二维 FFT 的答案了。
SPOJ8372 TSUM - Triple Sums
- 容斥+NTT
P4841 [集训队作业2013] 城市规划
- 之前有 \(\ln\) 的做法，不过这道题可以用多项式求逆做

习题

更高阶的多项式算法

分治 FFT

参考

分治+FFT

本质上这一部分应该叫 分治+FFT 或 分治套FFT 而不是 分治FFT。

经典运用是求形如 \(F(1, n) = \prod_{i=1}^n (1+a_ix)\) 的多项式。

如果直接计算的话，由于 \(n\) 阶多项式和 \(m\) 阶多项式相乘的复杂度是 \(O((n+m)\log(n+m))\)（FFT）或 \(O(nm)\) 暴力，对于 \(m=2\) 来说至少也是 \(O(n)\) 的。所以直接计算是 \(1+2+\cdots+n=O(n^2)\) 的。

考虑 \((n+m)\log (n+m)\) 在 \(n\) 和 \(m\) 接近时会比较赚，所以考虑 cdq 分治。求 \(F(l, r)\) 时先求 \(F(l, mid)\) 和 \(F(mid + 1, r)\) 再乘起来，这样复杂度是 \(T(n) = 2T(\frac n2) + O(n \log n) = O(n\log^2 n)\) 的。

半在线卷积

考虑求解形如 \(F(x) = F(x)G(x) + H(x)\) 的多项式，其中 \(G(0) = 0\)，那么可以用分治 FFT 解决。（这种情况有时也可以解方程然后多项式求逆）

做法是考虑 cdq。求 \(f_{l..r}\) 时先求出 \(f_{l..mid}\)，然后将 \(f_{l..mid}\) 到 \(f_{mid+1,r}\) 的贡献用卷积求出来，然后再求 \(f_{mid+1..r}\)。

对于 \(F(x) = F(x)F(x) + H(x)\) 之类的多项式也可以做，不过有点区别。具体来说我们将 \(f_{l..mid}\times f_{1..mid}\) 对 \(f_{mid+1..r}\) 的贡献求出后再递归 \(f_{mid+1..r}\)。

循环卷积与 bluestein 算法

参考

bluestein 算法又称 Chirp-Z 变换。

其实在 NTT 中，如果我们取恰好 \(n\) 个点值而不是至少 \(2n\) 个点值，那么求出来的就是循环卷积。不过 \(n\) 有可能不是 \(2\) 的幂次，所以需要 bluestein 来计算任意个数个点值。

首先带入点值 \(\omega_n^i\)：\(F_k = \sum_{i=0}^n a_i \omega_n^{ik}\)。

然后发现 \(ik = \binom{i+k}{2} - \binom{i}{2} - \binom{k}{2}\)（考虑组合意义，即有两个盒子，每个盒子分别有 \(i\) 个球和 \(k\) 个球，求有多少种拿出两个球且分别属于两个盒子的方法），于是上式可以化为：

\[ \begin{aligned} F_k &=\sum_{i=0}^n a_i \omega_n^{\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}}\\ &=\omega_n^{\binom{k}{2}} \sum_{i=0}^n a_i \omega_n^{-\binom{i}{2}}\cdot \omega_n^\binom{i+k}{2}\\ &=\omega_n^{\binom{k}{2}} \sum_i A_{-i}B_{i+k}\\ \end{aligned} \]

其中 \(A_i = a_{-i}\omega_n^{-\binom{-i}{2}}\)，\(B_i=\omega_n^\binom{i}{2}\)。

然后就可以用卷积计算了。

裸题：POJ2821 TN's Kingdom III - Assassination

转置原理

以下仅供了解。

引入

参考1 参考2

给定过程矩阵 \(A\) 以及输入向量 \(a\)，求解输出向量 \(b=Aa\) 的算法，被称为线性算法。（又称线性变换）

对于一个线性算法 \(b=Aa\)，一定有另外一个类似的算法 \(b=A^Ta\)，我们称这两个算法 互为转置。

内容

转置原理 给出了两个互为转置的算法之间互相转化的方法。

对于一个可逆矩阵 \(A\)，我们可以讲它分解为若干初等矩阵的乘积 \(E_1E_2\cdots E_m\)，那么 \(b=E_1E_2\cdots E_ma\)。那么它的转置问题就是 \(b=A^Ta=E_m^TE_{m-1}^T\cdots E_1^Ta\)。

也就是说，对于一个线性算法，我们原来是不断将它左乘初等矩阵，那么它的转置问题就是不断地（倒序）左乘上初等矩阵的转置。

然后考虑一个初等矩阵和它转置之间的关系：

对于一个交换第 \(i\) 行和第 \(j\) 行的矩阵，它的转置和它是一样的
对于一个把第 \(i\) 行乘 \(v\) 加到第 \(j\) 行的矩阵，它的转置变成了把第 \(j\) 行乘 \(v\) 加到第 \(i\) 行。

所以我们只需要按照上面的规则将原做法进行转置，就可以得到转置问题的解法了。

当然，在实际操作中，为了方便，我们不会真的以初等矩阵为单位来拆分并转置，而是以整合后的矩阵为单位描述算法。

应用

离散傅里叶变换

观察 DFT 的矩阵：

\[ A = [\omega_n^{ij}]_{0\le i,j\le n} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1\\ 1 & \omega_n & \omega_n^2 & \cdots & \omega_n^{n - 1}\\ 1 & \omega_n^2 & \omega_n^4 & \cdots & \omega_n^{2(n - 1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \omega_n^{n-1} & \omega_n^{2(n-1)} & \cdots & \omega_n^{(n-1)(n-1)} \end{bmatrix} \]

我们发现它是关于主对角线对称的，也就是说 \(A=A^T\)。所以 DFT 的转置算法就是它本身。

加法卷积

对于多项式 \(F,G,H\) 的乘法 \(H=F\times G\)，如果我们把 \(F\) 看成输入，\(G\) 看成常量，\(H\) 看成输出，则有：

\[ H_k = \sum_{i=0}^k G_i F_{k-i} \]

于是我们可以得到 \(b=Aa\) 中 \(a=\begin{bmatrix}F_0\\ F_1\\ \vdots\\ F_n\end{bmatrix}\)，\(b=\begin{bmatrix}H_0\\ H_1\\ \vdots\\ H_n\end{bmatrix}\)，

\[ A= \begin{bmatrix} G_0 & 0 & 0 & \cdots & 0 & 0\\ G_1 & G_0 & 0 & \cdots & 0 & 0\\ G_2 & G_1 & G_0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ G_{n-1} & G_{n-2} & G_{n-3} & \cdots & G_0 & 0\\ G_n & G_{n-1} & G_{n-2} & \cdots & G_1 & G_0 \end{bmatrix} \]

也即 \(A_{ij} = [i\ge j]G_{i-j}\)。

于是 \(A^T_{i,j} = [i\le j]G_{j-i}\)，\((A^Ta)_i=\sum_{j=0}^nA_{i,j}b_j=\sum_{j=i}^nG_{j-i}F_j=\sum_{j=0}^{n-i}G_jF_{j+i}\)

于是加法卷积的转置问题是减法卷积，即差卷积。（下面用 \(\times^T\) 表示差卷积）

多项式多点求值

参考

考虑多项式 \(F\) 和序列 \(X\)，求出答案序列 \(Y_i=F(X_i)\)。那么：

\[ Y_k = F(X_k) = \sum_{i}F_iX_k^i \]

于是 \(A_{ij} = X_i^j\)，所以 \(A^T_{ij} = X_j^i\)。

那么转置问题就是 \(Y_k = \sum_{i}F_iX_i^k\)，也就是求：

\[ \begin{aligned} G(x) &=\sum_{k=0}^nY_kx^k\\ &=\sum_{k=0}^nx^k\sum_{i=0}^nF_iX_i^k\\ &=\sum_{i=0}^nF_i\sum_{k=0}^nx^kX_i^k\\ &=\sum_{i=0}^n\frac{F_i}{1-xX_i} \end{aligned} \]

这是一个经典的分治 FFT 问题。为了下面讨论方便，我们把流程形式化地写出来：

对于区间 \([l, r)\)，我们维护分母 \(Q_{[l, r)} = \prod\limits_{i=l}^{r-1}(1-xX_i)\) 和分子 \(\sum\limits_{k=l}^{r-1} F_k \prod\limits_{\substack{i\in [l, r)\\i\ne k}}(1-xX_i)\)，那么有：

\[ \begin{aligned} Q_{[l, r)} &= Q_{[l, m)}\times Q_{[m, r)}\\ P_{[l, r)} &= P_{[l, m)}\times Q_{[m, r)} + P_{[m, r)}\times Q_{[l, m)} \end{aligned} \]

最终答案就是 \(F = P_{[0, n)}\times \frac{1}{Q_{[0, n)}}\)。

于是我们可以设计出转置问题的算法：

\(Q\) 与输入无关，故视为常数，先预处理
求出 \(P_{[0, n)} = F\times^T \frac{1}{Q_{[0, n)}}\)
从上到下 cdq。转置问题的贡献图是 \(P_{[l, m)}\stackrel{\times Q_{[m, r)}}{\longrightarrow}P_{[l, r)}\stackrel{\times Q_{[l, m)}}{\longleftarrow}P_{[m, r)}\)，所以原问题的贡献图是 \(P_{[l, m)}\stackrel{\times^T Q_{[m, r)}}{\longleftarrow}P_{[l, r)}\stackrel{\times^T Q_{[l, m)}}{\longrightarrow}P_{[m, r)}\)。

至此就完成了多点求值。

多项式快速插值

首先考虑拉格朗日插值公式：

\[ \begin{aligned} F(x) &=\sum_{i=1}^n y_i \prod_{j\ne i}\frac{x-x_j}{x_i-x_j}\\ &=\sum_{i=1}^n \frac{y_i}{\boxed{\prod_{j\ne i} (x_i-x_j)}}\prod_{j \ne i} (x - x_j) \end{aligned} \]

考虑设 \(g(x) = \prod_{i=1}^n (x-x_i)\)，那么框出来的部分就是 \(\dfrac{g(x_i)}{x-x_i}\)。由于它是连续可导的，且在除 \(x=x_i\) 以外的点都和 \(\prod_{j\ne i} (x-x_j)\) 值相同。所以 \(x-x_i\) 是它的可去间断点。取极限得 \(\lim_{x\to x_i}\dfrac{F(x)}{x-x_i}=\lim_{x\to x_i}F'(x) = F'(x_i)\)。

后面就考虑分治 FFT：

\[ \begin{aligned} F_{[l, r)} &=\sum_{i=l}^r \frac{y_i}{g'(x_i)} \prod_{j\ne i} (x-x_j)\\ &=F_{[l, mid)}\prod_{j=mid}^{r-1}(x-x_j) + F_{[mid, r)}\prod_{j=l}^{mid-1}(x-x_j) \end{aligned} \]

连续整数拉格朗日插值

应该不是属于我讲的部分？

给个板子例题吧：CF622F The Sum of the k-th Powers

例题

UOJ182 a^-1 + b problem
- 找性质
- 推柿子
- 多点求值！
P5450 [THUPC2018] 淘米神的树
- 先考虑一个黑点？
- 建立虚点，转化成基环树
- 推柿子！
- 多点求值！
P3321 [SDOI2015] 序列统计
- 加法怎么做？
  - 需要循环卷积？
- 模意义下的乘法转加法？
  - 原根！
P5293 [HNOI2019] 白兔之舞
- 矩阵乘法
- 单位根反演

习题

P4191 [CTSC2010] 性能优化（注意此题不是 bluestein 裸题）
AGC060D Same Descent Set（较难）

上升幂、下降幂与斯特林

快速计算第一、二类斯特林数的一行、列

参考 OI Wiki

模板题：P5408，P5409，P5395，P5396

下降幂多项式

形如 \(F(x) = \sum_{i=0}^n f_i x^{\underline{i}}\) 的多项式叫做下降幂多项式。

类似的有上升幂多项式，由于和下降幂对称，而且也不常用，所以下面都不讲。

下降幂多项式多点求值和插值

参考这里

下降幂多项式乘法

先多点求值再插值即可。

下降幂多项式与普通多项式互转

有两种方法。

第一种比较无脑，但是常数较大，即先将其中一个多点求值，再将另一个快速插值。

第二种是分治 FFT/NTT，具体可以参考题解区（下降转普通，普通转下降）

例题

第一类斯特林数的一行
UOJ269 【清华集训2016】如何优雅地求和

习题

其它应用

CF528D Fuzzy Search
- 多项式×字符串
HDU7054 Yiwen with Formula

上面的题目比较有针对性，一般都是针对章节的较为模板化的题目。

如果想要做多项式杂题可以看 grass8cow 的专题（题解，密码是经典密码）