MornStar @ 2025-02-07 15:12:17
想问一下这种写法是否适用于任何场合：
NTT(f,d,1); for(int i=0;i<d;i++) { f[i]=qpow(f[i],x); } NTT(f,d,-1);
如果这种写法可以完全适用，那么 O(n\log^2 n) 的倍增快速幂和普通的 ln+exp 有什么特殊之处？
by zhouyuhang @ 2025-02-07 15:18:40
不适用于任何场合。
时刻牢记长度为 l 的 dft/idft 实际上做的是长为 l 的循环卷积，也即实际上多项式 F(x) \bmod (x ^ l - 1) 的结果。一般我们取 l = 2 ^ k，其中 2 ^ k 要大于乘出来的多项式长度，因此不会出错；但是多项式快速幂的结果长度非常大，这样做自然就是错的。