瞎讲：FFT三次变二次优化
2020年了我怎么还是没有学会任意模数NTT……发现自己多项式的技能没有点的还有很多。处理任意模数NTT有一系列的方法，其中有个看起来比较优的算法需要FFT三次变二次优化。众所周知，普通的FFT长这样：假设是多项式A(x)A(x)A(x)和B(x)B(x)B(x)求卷积，首先求DFT(A)DFT(A)DFT(A)和DFT(B)DFT(B)DFT(B)，两者相乘后求IDFTIDFTIDFT这样算了三次DFTDFTDFT。接下来的算法可以将三次DFTDFTDFT优化成两次。设P(x)=A(x)
