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

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

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

[ ]

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

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

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

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

(icdot 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),jin[0,d-1])，可以得到合并式子

(egin{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'_{imod frac{n}{d}})end{aligned})

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

(O(nsum p_i)=O(ncdot max{p_i} log n))

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

[ ]

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

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

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