多项式指定大小的单位根点值式求解(含Bluestein’s Algorithm)

下面的阐述建立于存在$n$阶单位根的前提下

(如果是NTT，必须满足$n|(P-1)$ ，否则单位根可能会变成一个复杂的多维向量)

$\$

用卷积解决多项式与点值式的转化:Bluestein’s Algorithm

设最终求得的点值式为$f(x^k)=\sum a_i\cdot \omega_n^{i k}$

其中指数为$ik$，有一种简单的转化$i\cdot k=\cfrac{i^2+k^2-(i-k)^2} {2}$

由于在模意义下，$x^{\frac{i} {2} }$次(二次剩余)是一个非常麻烦的东西，所以考虑一个更优的转化

$i\cdot k=C(i+k,2)-C(i,2)-C(k,2)$

这条式子的组合意义是：从集合$i,k$分别选一个，等价于从$i+k$选两个减去在$i,k$内部选两个

通过这样的转化，我们可以对于每一个$a_i$计算其对于每个$f(x^k)$的贡献

具体过程是简单的构造卷积，这里省略

$\$

需要了解的是，多项式卷积的FFT/NTT不止适用与于二元分治

对于多项式$F(x)$的$d$元分治，设分治子问题的答案为$G_j(x’_i),j\in[0,d-1]$，可以得到合并式子

$\begin{aligned} F(x_i)=\sum_{j=0}^{d-1}x_i^jG_j(x_i^d)=\sum_{i=0}^{d-1}x_i^jG_j(x'_{i\mod \frac{n} {d} })\end{aligned}$

对于$n$进行质因数分解，得到$n=\prod p_i$，带入上面的式子，带入$p_i$元分治强行求解，可以认为最终复杂度为

$O(n\sum p_i)=O(n\cdot \max\{p_i\} \log n)$

因此，这种方法使用于$p_i$较小的情况

$\$

DFT的卷积是溢出的，$x^i$会溢出到$x^{i\mod n}$，系数之间存在着循环关系

我们可以利用$n$元卷积做到指定大小的循环卷积，可以处理一些特定问题

例题: [CTSC2010]性能优化(使用$O(n\log n\log C)$的快速幂无法通过，尚未尝试Bluestein’s Algorithm)