坑了个爹的FFT……原理只了解到卷积那一步……怎么转换成整系数而非sincos乱搞的系数那个完全不了解……权当背代码了……

其实代码灰常好写……根本不像我想像的那样超级复杂！代码的关键在于如何选P（）……

其实P是很好选的，对于一个n，用各种c测试下是不是素数就可以了……一般将P固定起来。我用的是。为什么用21位呢？再大一点就要unsigned了，不方便（尽管GAOA上建议使用）。小一点又会过于小。

选了P以后要计算它的原根……这个就有点晕了，不过我可以告诉你，479<<21^1的原根是3，15<<27^1的原根是31……背出来就OK了。

由于我自己也不是完全懂……所以不细讲了……

蝴蝶操作：。原根的幂可以先预处理出来。

具体操作是先对AB进行FFT，再让B成为卷积之积，然后映射回A上做IDFT。由于我们换上了P，所以特别方便，只要把B倒着放回A里面，然后直接对A做FFT，除以n就是乘上！神奇吧！

对于迭代时那个奇葩的04261537……最简单的方法是写个rev函数将i的二进制位倒过来……时间复杂度是O(lgn)的。GAOA上说有更好的方法，但没说，于是我YY了一个。注意到：

4=0+4

2=0+2，6=4+2

1=0+1，5=4+1，3=2+1，7=6+1

发现好像可以a[0]=x[0]后，先推1个，然后用前两个推下两个，再用前四个推下四个……就解决了。

总的要把握宁滥勿缺的原则……那啥……搞大点总不会错的嘛。

下面是代码……只有31行……不过估计没人看得懂 - -