背景:本蒟蒻正在学习FFT,BFS了七八篇博客,但基本上关于为什么在求值时要使用单位复数根只是简略的过了一下,懵逼了一个下午(当然也可能是我悟性太差了)
1,为什么FFT求值时要使用单位复数根?
2,为什么用了单位复数根,计算每个子问题的时候只需要计算一半?(蒟蒻看了亿堆博客,似乎是因为 wnkw_{n}^{k}wnk 与 wnk+n2w_{n}^{k+\frac{n}{2}}wnk+2n 只有符号不同,但不知道理解有没有偏差)