目录
多项式 4
循环卷积
定义
$$c_k=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}[i+j\bmod p=k]a_ib_j$$
性质
对序列 $A,B$ 做长度为 $n$ 的 $\text{FFT}$ 等价于求序列 $A,B$ 的长度为 $n$ 的循环卷积。
考虑单位根反演证明
$$ \begin{equation}\begin{split} c_k&=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}[i+j\bmod p=k]a_ib_j\\ &=\frac 1n\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\sum_{d=0}^{n-1}w_n^{d(i+j-k)}a_ib_j\\ &=\frac 1n\sum_{d=0}^{n-1}w_n^{-dk}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}w_n^{di}a_iw_n^{dj}b_j\\ &=\frac 1n\sum_{d=0}^{n-1}w_n^{-dk}\left(\sum_{i=0}^{n-1}a_iw_n^{di}\right)\left(\sum_{j=0}^{n-1}b_jw_n^{dj}\right) \end{split}\end{equation} $$ 不难发现 $\left(\sum_{i=0}^{n-1}a_iw_n^{di}\right)\left(\sum_{j=0}^{n-1}b_jw_n^{dj}\right)$ 即为原来的 $\text{DFT}$ 过程，$\frac 1n\sum_{d=0}^{n-1}w_n^{-dk}$ 即为原来的 $\text{IDFT}$，证毕。
事实上普通的卷积计算相当于长度为 $2^n$ 的循环卷积计算，只是循环卷积长度大于 $C$ 序列的长度，所以循环卷积结果即为普通卷积结果。
值得一提的是，循环卷积的求逆、快速幂等操作直接对 $\text{DFT}$ 的点值进行相应运算即可。
另外注意到 $f(w^{-k})=f(w^{n-k})$，于是循环卷积的 $\text{IDFT}$ 过程可以通过将序列 $[1,n-1]$ 部分翻转再 $\text{DFT}$ 的方式实现。
Cooley–Tukey FFT algorithm
算法实现
普通 $\text{DFT}$ 过程是将序列根据奇偶幂次分成两段经行递归，现考虑将序列分成 $d$ 段进行递归，设
$$f(x)=a_0+a_1x^1+a_2x^2+\cdots a_{n-1}x^{n-1},f_k(x)=a_kx^k+a_{d+k}x^{d+k}+a_{2d+k}x^{2d+k}+\cdots+a_{n-d+k}x^{n-d+k}(0\le k\lt d),m=\frac nd$$
于是有
$$f(w_n^{im+j})=\sum_{k=0}^{d-1}w_n^{(im+j)k}f_k(w_n^{(im+j)d})=\sum_{k=0}^{d-1}w_n^{(im+j)k}f_k(w_n^{in}w_n^{jd})=\sum_{k=0}^{d-1}w_n^{(im+j)k}f_k(w_m^j)$$
计算出每个点值的时间为 $O(d)$，每层共 $O(n)$ 个点值。设 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，于是总时间复杂度 $O\left(n\sum_{i=1}^k p_i\alpha_i\right)$。
算法例题
给定长度为 $n$ 的序列 $A,B$，计算 $AB^C$ 的长度为 $n$ 的循环卷积模 $n+1$ 意义下的值。
数据保证 $n+1$ 为素数，$n\le 5\times 10^5$，$n$ 的最大质因子不超过 $10$。
题解
$\text{Cooley–Tukey FFT algorithm}$ 板子题，$\text{DFT}$ 后直接对点值快速幂即可，时间复杂度 $O(7n\log n)$
Bluestein's Algotithm
算法实现
考虑 $\text{DFT}$ 过程，有
$$ \begin{equation}\begin{split} y_k&=\sum_{i=0}^{n-1}a_iw_n^{ki}\\ &=\sum_{i=0}^{n-1}a_iw_n^{{k+i\choose 2}-{k\choose 2}-{i\choose 2}}\\ &=w_n^{-{k\choose 2}}\sum_{i=0}^{n-1}\left(a_iw_n^{-{i\choose 2}}\right)w_n^{{k+i\choose 2}} \end{split}\end{equation} $$ 其中 ${n\choose 2}$ 表示组合数，易知上式可以通过普通卷积求解。
考虑 $\text{IDFT}$ 过程，同样有
$$ \begin{equation}\begin{split} a_k&=\frac 1n\sum_{i=0}^{n-1}y_iw_n^{-ki}\\ &=\frac 1n\sum_{i=0}^{n-1}y_iw_n^{-{k+i\choose 2}+{k\choose 2}+{i\choose 2}}\\ &=\frac 1nw_n^{{k\choose 2}}\sum_{i=0}^{n-1}\left(y_iw_n^{{i\choose 2}}\right)w_n^{-{k+i\choose 2}} \end{split}\end{equation} $$ $\text{ }$
算法例题
给定一个二维 $[L+1]\times n$ 的空间，其中 $(u_1,v_1)\to (u_2,v_2)$ 有 $w_{v_1,v_2}$ 条重边。
假设起点为 $(0,x)$，终点为 $(\ast,y)$($\ast$ 为任意值)，路径长度 $m$ 定义为路径的边数。
对每个 $0\le t\lt k$，求满足所有 $m\equiv t\pmod k$ 且横坐标单增的路径数模 $p$ 意义下的值。
数据保证 $p$ 为素数，$10^8\le p\le 2^{30},k\mid p-1,1\le k\lt 65536,1\le n\le 3,L\le 10^9$。
题解
假设 $f_{a,b}$ 表示 $m=a$ 且 $y=b$ 的路径数，$g_{a,b}$ 表示将空间的 $X$ 维消去后 $m=a$ 且 $y=b$ 的路径数。
于是有状态转移方程
$$g_{a,b}=\sum_{i=1}^n g_{a-1,i}w_{i,b}\text{ },\text{ }f_{a,b}={L\choose a}g_{a,b}$$
设矩阵
$$W=\begin{bmatrix}w_{1,1} & \cdots & w_{1,n} \\ \vdots &\ddots & \vdots \\ w_{n,1} &\cdots & w_{n,n}\end{bmatrix}$$
设 $G_i=(g_{i,1}\cdots g_{i,n})$，于是有 $G_i=G_0W^i$。
考虑单位根反演，设 $w_k\equiv g^{\frac {p-1}k}\pmod p,g$ 为 $p$ 的原根，有
$$ \begin{equation}\begin{split} \text{ans}_t&=\sum_{i=0}^Lf_{i,y}[i\bmod k=t]\\ &=\frac 1k\sum_{i=0}^Lf_{i,y}\sum_{j=0}^{k-1}w_k^{(i-t)j}\\ &=\frac 1k\sum_{j=0}^{k-1}w_k^{-tj}\sum_{i=0}^L f_{i,y}w_k^{ij} \end{split}\end{equation} $$ 根据二项式定理，有 $$\sum_{i=0}^L w_k^{ij}(f_{i,1}\cdots f_{i,n})=\sum_{i=0}^L w_k^{ij}{L\choose i}(g_{i,1}\cdots g_{i,n})=G_0\sum_{i=0}^L {L\choose i}\left(w_k^jW\right)^i=G_0\left(w_k^jW+I\right)^L$$ 于是根据矩阵快速幂可以 $O(kn^3\log L)$ 计算出所有 $h_j=\sum_{i=0}^L f_{i,y}w_k^{ij}(0\le j\lt k)$。
于是有
$$\text{ans}_t=\frac 1k\sum_{i=0}^{k-1}w_k^{-ti}h_i$$
发现上式就是 $\text{Bluestein's Algotithm}$ 的 $\text{IDFT}$ 过程，直接求解时间复杂度 $O(k\log k)$。
总时间复杂度 $O(kn^3\log L)$，主要用于计算矩阵快速幂。
常系数齐次线性递推
算法简介
给定 $a_n=f_1a_{n-1}+f_2a_{n-2}+\cdots +f_ka_{n-k}$ 以及 $a_0,a_1\cdots a_{k-1}$，询问 $a_n$ 的值。时间复杂度 $O(k\log k\log n)$。
算法实现
考虑求斐波那契数列过程，$f_5=f_4+f_3=2f_3+f_2=3f_2+2f_1=5f_1+3f_0$。
从多项式角度上考虑该过程，$f_n=f_{n-1}+f_{n-2}$ 的特征多项式为 $x^2-x-1$，并且有
$$ \begin{matrix} &0x^0&+0x^1&+0x^2&+0x^3&+0x^4&+1x^5\\ \equiv&0x^0&+0x^1&+0x^2&+1x^3&+1x^4&+0x^5\\ \equiv&0x^0&+0x^1&+1x^2&+2x^3&+0x^4&+0x^5\\ \equiv&0x^0&+3x^1&+2x^2&+0x^3&+0x^4&+0x^5\\ \equiv&3x^0&+5x^1&+0x^2&+0x^3&+0x^4&+0x^5&\pmod {x^2-x-1} \end{matrix} $$
于是 $f_5=\left(x^5\bmod {x^2-x-1}\right)\cdot (f_0,f_1)=(3,5)\cdot (f_0,f_1)$。
以此类推，对 $a_n=f_1a_{n-1}+f_2a_{n-2}+\cdots +f_ka_{n-k}$，其特征多项式为 $x^k-f_1x^{k-1}-f_2x^{k-2}-\cdots -f_k$。
于是 $a_n= \left(x^n\bmod {x^k-f_1x^{k-1}-f_2x^{k-2}-\cdots -f_k}\right)\cdot (a_0,a_1\cdots a_{k-1})$。
其中 $\left(x^n\bmod {x^k-f_1x^{k-1}-f_2x^{k-2}-\cdots -f_k}\right)$ 可以通过快速幂与多项式带余除法 $O(k\log k\log n)$ 计算。
发现每次带余除法计算时 $g(x)$ 都是固定的，可以考虑先计算出 $\frac 1{g^R(x)}$ 减小常数。
多项式多点求值
算法简介
给定一个 $n$ 次多项式 $f(x)$，求 $f(a_i)(1\le i\le m)$。时间复杂度 $O(n\log n+m\log^2 m)$，空间复杂度 $O(m\log m)$。
算法实现
设 $f(x)=c_0+c_1x+c_2x^2\cdots c_nx^n$，于是有
$$ \begin{equation}\begin{split} f(x)-f(x_0)&\equiv c_0-c_0+c_1(x-x_0)+c_2(x^2-x_0^2)\cdots +c_n(x^n-x_0^n)\\ &\equiv c_1(x-x_0)+c_2(x-x_0)(x+x_0)\cdots +c_n(x-x_0)(x^{n-1}+x^{n-2}x_0+\cdots +x_0^{n-1})\\ &\equiv 0\pmod {x-x_0} \end{split}\end{equation} $$ 即 $f(x_0)\equiv f(x)\pmod {x-x_0}$，于是如果能快速计算 $f(x)\bmod {x-x_0}$，就可以得到 $f(x_0)$。
记 $f_{l,r}(x)\equiv f(x)\pmod {\prod_{i=l}^r (x-a_i)}$，于是有 $f_{l,r}(x)\equiv f_{l,m}(x)\pmod{\prod_{i=l}^m (x-a_i)},f_{l,r}(x)\equiv f_{m+1,r}(x)\pmod{\prod_{i=m+1}^r (x-a_i)}$。
考虑 $O(m\log^2 m)$ 自底向上建立线段树，每个节点存储 $\prod_{i=l}^r (x-a_i)$ 的多项式。
然后 $O(m\log^2 m)$ 自顶向下进行带余除法，跑到叶子节点就可以得到每个 $f(a_i)$ 的值。
注意根节点需要提前进行带余除法，同时该算法常数较大，考虑常数优化。
不妨令 $r-l$ 小于某个固定值 $L$ 后采用 $O(L^2)$ 暴力秦九韶展开，秦九韶复杂度为 $O(\cfrac mLL^2)=O(mL)$。
于是总时间复杂变为 $O(n\log n+m\log m(\log m-\log L)+mL)$，经检验 $m=64000$ 时取 $L=640$ 效果较佳。
多项式快速插值
算法简介
给定 $n$ 个点 $(x_i,y_i)$，求次数不超过 $n-1$ 次的多项式 $f(x)$ 满足 $f(x_i)=y_i$。时间复杂度 $O(n\log^2 n)$，空间复杂度 $O(m\log m)$。
算法实现
根据拉格朗日插值法，有
$$f(x)=\sum_{i=1}^n y_i\prod_{j=1,j\neq i}^n \frac {x-x_j}{x_i-x_j}=\sum_{i=1}^n \cfrac {y_i}{\prod_{j=1,j\neq i}(x_i-x_j)}\prod_{j=1,j\neq i}^n x-x_j$$
设 $g(x)=\prod_{i=1}^n x-x_i$，根据洛必达法则，有
$$\prod_{j=1,j\neq i}^n x_i-x_j=\lim_{x\to x_i}\frac {g(x)}{x-x_i}=g'(x_i)$$
于是有 $f(x)=\sum_{i=1}^n \cfrac {y_i}{g'(x_i)}\prod_{j=1,j\neq i}^n x-x_j$。
考虑 $O(n\log^2 n)$ 分治乘法计算出 $g(x)$，再通过 $O(n\log^2 n)$ 多项式多点求值计算出所有 $g'(x_i)$。
设 $f_{l,r}(x)=\sum_{i=l}^r \cfrac {y_i}{g'(x_i)}\prod_{j=l,j\neq i}^r x-x_j$。考虑分治，有
$$ \begin{equation}\begin{split} f_{l,r}(x)&=\left(\sum_{i=l}^m \cfrac {y_i}{g'(x_i)}\prod_{j=l,j\neq i}^m x-x_j\right)\left(\prod_{j=m+1}^r x-x_j\right)+\left(\sum_{i=m+1}^r \cfrac {y_i}{g'(x_i)}\prod_{j=m+1,j\neq i}^r x-x_j\right)\left(\prod_{j=l}^m x-x_j\right)\\ &=f_{l,m}(x)\left(\prod_{j=m+1}^r x-x_j\right)+f_{m+1,r}(x)\left(\prod_{j=l}^m x-x_j\right) \end{split}\end{equation} $$
于是可以 $O(n\log^2 n)$ 完成分治，总时间复杂度 $O(n\log^2 n)$。
