标签：OI 卷积 多项式 FFT ACM 变换 快速 乘法
ACM&OI 基础数学算法专题
一、FFT基础
- 拉格朗日插值
- 复数的运算性质和几何性质
- 单位根和单位根反演
- 快速傅里叶变换（FFT）的分治实现
- 快速傅里叶逆变换（IFFT）
- 快速傅里叶变换的倍增实现
二、FFT进阶
- 快速数论变换（NTT）
- 任意模数多项式乘法-多模数快速数论变换
- 任意模数多项式乘法-MTT
- 长多项式的乘法
- 简单的加法卷积、减法卷积、循环卷积和带模的乘法卷积
三、多项式基础运算
- 多项式乘法逆
- 多项式整除
- 多项式取模
- 多项式求导积分
- 多项式对数
- 多项式牛顿迭代
- 多项式指数
- 多项式开方
- 多项式快速幂和多项式幂次
- 多项式三角函数和多项式反三角函数
- 多项式线段树分治
- 多项式启发式合并
- 多项式cdq分治
四、多项式进阶
- 多项式加速的线性递推
- 基于多项式取模的多项式多点求值
- 基于转置原理的多项式多点求值
- 多项式快速插值
- BlueStein算法/CZT
- 多项式线性变换
- exCZT
- 多项式的连续点值平移
- 基于分块的带变元矩阵乘法
五、其它卷积
- 指数型生成函数的卷积
- 快速沃尔什变换（FWT）
- k进制快速沃尔什变换
- 广义沃尔什变换（exFWT）
- 占位多项式和二维FFT
- 子集卷积（or-FST, xor-FST）
- 高维FFT
- 狄利克雷型生成函数的卷积
- gcd卷积和lcm卷积
标签：OI,
卷积,
多项式,
FFT,
ACM,
变换,
快速,
乘法
From： https://www.cnblogs.com/JustinRochester/p/17036805.html