生成函数讲稿

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

定位: 大家都可以来听听吖(我估计包括高二大部分人都不会

参考

简单线性代数前置知识

  1. 矩阵
    • 矩阵的定义:数表
      • \(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\) 可表示为若干初等矩阵的乘积
  2. 行列式
    • \(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)
  3. 余子式、代数余子式
    • 定义
      • 余子式:\(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)

矩阵树定理

  1. Binet-Cauchy 定理
  2. 基尔霍夫矩阵
  3. 引理
  4. 证明

Bonus: Cayley 公式

习题

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


普通生成函数 OGF

定位: 中等偏低

参考

引入

  1. 定义
    • ordinary generating function
    • 数乘、卷积定义
  2. 求 Fibonacci

简单运算

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

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

然后有一些变换:

  1. 平移
    • \(\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)\)
  2. 拉伸
    • \(\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)\)
  3. 扩倍(数乘)
    • \(\langle a_0, a_1, a_2, \cdots \rangle \longrightarrow \langle ka_0, ka_1, ka_2, \cdots \rangle\)
    • \(F(x) \to kF(x)\)
  4. 乘等比数列
    • \(\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)\)
  5. 求导
    • \(\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+1)^n\)
  • \(\sum\limits_{i=0}(-1)^i\dbinom{n}{i} = (1-x)^n\)
  • \(\sum\limits_{i=0}\dbinom{n+i}{i} = \dfrac{1}{(1-x)^{n+1}}\)
  • \(\sum\limits_{i=1}\dfrac{1}{i!} = -\ln (1-x)\)

求递推式的封闭形式——常系数齐次线性递推

注:这里讲的仅仅是求出通项,如果想看真正的常系数齐次线性递推和 BM,可以看 OI Wiki(常系数齐次线性递推BM)。

本质上就是自己凑自己。

考虑假设有 \(\sum\limits_{i=0}^k c_i f_{n-i} = 0\),即给出了一个递推式,那么我们可以求得 \(f\) 的通项。

我们令 \(f\) 的生成函数为 \(F\)

首先考虑凑出 \(c_t f_{n-t}\),即我们构造 \(F_t\) 使得 \([x^n]F_t(x) = [n\ge t] c_t f_{n-t}\)
具体构造方法也比较简单:\(F_t(x) = c_t x^t \left(F(x) - \sum\limits_{i=0}^{k-t-1} f_i x^i \right)\)

然后考虑代入原式:\(\sum\limits_{t=0}^k F_t(x) = 0\),整理可得 \(\left(\sum\limits_{t=0}^k c_tx^t\right) F(x) = \sum\limits_{t=0}^{k-1}\left(c_t x^t \sum\limits_{i=0}{k-t-1} f_i x^i\right)\)

设左边为 \(C(x)F(x)\),右边为 \(P(x)\),那么我们就得到了 \(F(x)\) 的生成函数 \(\dfrac{P(x)}{C(x)}\)。后面的内容可以用多项式计算,或者手动分式分解。

应用

没啥用 我不知道有啥用。

例题

  1. \(a_n = 8a_{n-1} + 10^{n - 1}\)\(a_1=9\),求 \(a\) 的通项公式。
  2. 生成函数推 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} \]

  1. 请尝试用生成函数方法证明下面两个问题的答案相等:(Bonus: 其实这个可以建立双射,留作思考题
    • \(n\) 分为若干份,每份为正奇数的方案数
    • \(n\) 分为若干个不同正整数之和的方案数
  2. 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 那里)
  • 五边形数定理

指数生成函数

定位: 中等难度

参考

引入

  1. 定义
    • exponential generating function
    • 数乘、卷积定义

简单运算

  1. \(\langle 1, 1, 1, \cdots \rangle {\overset{\mathbf{EGF}}{\longrightarrow}} e^x\)
    • 泰勒展开
  2. \(\langle 1, -1, 1, -1, 1, \cdots \rangle {\overset{\mathbf{EGF}}{\longrightarrow}} e^{-x}\)
  3. \(\langle c^0, c^1, c^2, \cdots \rangle {\overset{\mathbf{EGF}}{\longrightarrow}} e^{cx}\)
  4. \(\langle 1, 0, 1, 0, 1, 0, \cdots \rangle {\overset{\mathbf{EGF}}{\longrightarrow}} \dfrac{e^x+e^{-x}}{2}\)
  5. \(\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

  1. EGF 卷积——组合对象的“归并”
    • OGF: {AAA}×{BBB}={AAABBB}(集合的合并)
    • EGF: (AAA)×(BBB)={(AAABBB),(AABBAB),(ABBAAB),(BBAAAB),……}\(\binom{3+4}{3}\) 种(序列的归并)
  2. 对 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)\)

例题

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

习题

  1. POJ3734 Blocks(无需 FFT/NTT)
  2. POJ1322 Chocolate(无需 FFT/NTT)
  3. P4389 付公主的背包(需要 FFT/NTT)

多项式全家桶

定位: 简单(这部分就是板子而已啊

参考

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

FFT 与 NTT

移步我的博客

自行了解: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\)

多项式 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}\)

例题

模板题

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

习题

  1. HDU-4609 3-idiots
  2. BZOJ3771 Triple
  3. UVA12298 Super Poker II
  4. P3723 [AH2017/HNOI2017] 礼物
  5. CF623E Transforming Sequence(较难)

插播:快速求第一、二类斯特林数的一行


更高阶的多项式算法

定位: 较难

分治 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)}}\)

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

  1. \(Q\) 与输入无关,故视为常数,先预处理
  2. 求出 \(P_{[0, n)} = F\times^T \frac{1}{Q_{[0, n)}}\)
  3. 从上到下 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

例题

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

习题

  1. P4191 [CTSC2010] 性能优化(注意此题不是 bluestein 裸题)
  2. AGC060D Same Descent Set(较难)

上升幂、下降幂与斯特林

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

参考 OI Wiki

模板题:P5408,P5409,P5395,P5396

下降幂多项式

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

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

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

参考 这里

下降幂多项式乘法

先多点求值再插值即可。

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

有两种方法。

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

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

例题

  1. UOJ269 【清华集训2016】如何优雅地求和

习题

  1. P6620 [省选联考 2020 A 卷] 组合数问题
  2. CF1278F Cards

其它应用

  1. CF528D Fuzzy Search
    • 多项式×字符串
  2. HDU7054 Yiwen with Formula

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

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