1. 多项式乘法（卷积）
简单来说，选取 \(\omega_n^k\) 代入，DFT 转化成点值表达式后相乘后再 IDFT。
把 FFT 的 \(\omega_n^k\) 换成 \(g^{\left\lfloor\frac{mod-1}{k}\right\rfloor}\)，其中 \(g\) 为 \(mod\) 的原根。
模板
P1919 【模板】A*B Problem 升级版（FFT 快速傅里叶变换）：注意处理进位。
循环移位或子串匹配问题
[ABC291G] OR Sum：按位计算每个循环移位的贡献，翻转 \(B\)，做异或卷积即可。异或卷积可以拆成两个乘法卷积。
[ABC196F] Substring 2：同样是快速计算每个位置开始匹配的最大匹配位数，翻转 \(T\) 后做异或卷积。
2. 多项式快速幂
指数很小的时候直接对点值求 \(k\) 次方即可，也可以倍增。
完全背包
CF1096G Lucky Tickets：构造多项式之后快速幂即可。
标签：卷积,多项式,FFT,异或,模板,乘法 From： https://www.cnblogs.com/zltzlt-blog/p/17387698.html