详细的还是翻书吧，总之都是并行地求多项式在1的各个n次根处的值，fft用的复数根，ntt用的是关于某个容易求mod的素数m的Z/mZ上1的n次原根的各个方幂。具体做的时候fft就是做一份三角函数表，ntt也可以做表，不过我好像是没做（好久前写的代码，细节都有懵了，昨天倒是调出了那些汇编里面有bug）。关键还是要消递归（就是那个nttreorder里面做的）吧，不消递归很多时间都要浪费在元素的复制上。
估算了一下时间（因为没有优化），快速变换用在这个题上还是绝对的牛刀杀鸡。若不是你在这儿说“为什么没人用n^lg3或者nlgn*lglgn的算法呢：）”我大概会先做了一个schoolboy multiplication了。

• 如果你有时间，可以试试看就单纯的高精度，用int64来每个单元多存几位 (31) hawk 2005-03-29 15:58:25
  • 本来是一个uint每个存四位，加42次进位一次，慢死了；改成uint64每个存8位，加1844次进位一次，203ms (0) cpp051200448264 2005-03-29 16:06:25
    • xiaomi那个好像就是integer，每个存4位，也挺快 (0) hawk 2005-03-29 16:07:43
      • 是3位，uint64可以存16位没问题吧，integer存八位 (22) hawk 2005-03-29 16:09:40
        • uint存满的话应该也可以，就是每乘一次就要有一次除法来调整，具体看怎么折衷吧。uint64存满纯用C会很难调整（又想到了汇编fpu） (26) c0500448264 2005-03-29 16:14:59
      • 无语了，接着再ft了，用uint就立马tle了 (0) c0500448264 2005-03-29 16:09:52
        • 存同样位数不如int64快？ (0) hawk 2005-03-29 16:13:27