在之前的DFT中有n^2的循环卷积

考虑式子为

循环卷积与任意长度FFT

的暴力卷积

拆分nk为循环卷积与任意长度FFT

对于Xk,k^2/2是常值

于是

循环卷积与任意长度FFT

可以发现后半部分是关于n和(k-n)的卷积。

可以得到点值。

逆运算可以推出相对的式子即可。