爆栈啦！！！！>_<

..............................

回复 @Mike is Fool : 嗯，我和你出的问题一模一样。

我的NTT是3s，夹心的NTT是1s……
我选择死亡

发个FFT算法流程的演示（伪）：
http://blog.csdn.net/wmdcstdio/article/details/44750885（公式预警）

回复 @Chenyao2333 :
我只是觉得自己代码力太差怕用fft精度写残……所以就学了个数论的……

为啥我看到还有叫NTT的东西我就不太想玩了呢。Orz@Asm.Def

回复 @ljz :
这位同学已经退役了。。。我帮你粘贴一下吧http://paste.ubuntu.com.cn/2140247

回复 @GDFRWMY :
pascal代码，能否借蒟蒻一看？

难道我是这里第一份NTT？好吧其实NTT中大量的素数取模运算似乎决定了它会比一般的fft慢一些- -
这里附一份暴力找单位根和素数的代码
网上关于ntt的资料似乎不太够啊。。。我在考虑明年暑假要不要写个ntt的全面介绍→_→

听杜神讲了FFT感觉不错【参见楼下的蝴蝶打法】
先get到两数的DFT(奇偶序列合并 $T(n) = T(n/2) + O(n)$ )
直接 $(c)k = (a)k*(b)k$
然后计算iDFT
最后进位 $O(logn)$

递归的fft真是。。。慢。。。。

亵渎了神题。

强杀前6个点，求大神讲解后4个点

我没写FFT，压九位加常数优化，过了。。去注释1.2K的样子。。

回复 @cstdio :
说得对，点赞

@法法桶 你叫这个名字还不写FFT……什么心态……

补充一句：以后再也不看算导了。。。。