还没有写代码，瞎讲一下。

三模数\(NTT\)

大概思路就是用三个满足\(a*2^b+1\)形式的质数来做\(NTT\)，
然后用数论方法搞出它的具体值（当长度为\(10^5\)级别时，卷积之后数字最多为\(10^{23}\)，所有同余的数中只有最小的那个在范围内）。
一般选\(469762049,998244353,1004535809\)，原根都是\(3\)
调用\(9\)次\(DFT\)，常数极大。

二模数\(NTT\)

和上面的那个思路差不多，只不过用一个大质数和一个小质数来搞。
long long相乘取模用强制转long double来解决。
质数取\(29*2^{57}+1\)和\(998244353\)，原根都是\(3\)。

拆分\(FFT\)

考虑将每个数拆成\(aW+b\)的形式，\(W\)取\(\sqrt P\)
结果长这样：\(acW^2+(ad+bc)W+bd\)
（这里\(a,b,c,d\)都应该理解成函数）
这样一个位置上的数字最大是\(10^{14}\)级别，精度好就可以接受。
调用\(7\)次\(DFT\)。

拆分\(FFT\)优化

分别计算：

将实部和虚部拆开来，就可以分别求出所需的\(ac\)、\(bd\)、\((ad+bc)\)。
于是只需求\((a+bi)\)和\((a-bi)\)和\((c+di)\)的\(DFT\)，以及两个乘积要做\(IDFT\)。
这样就可以优化到\(5\)次\(DFT\)。

利用FFT三次变两次中提到的性质（也就是共轭的两个多项式，求出其中一个的\(DFT\)之后可以\(O(n)\)地求出另一个的\(DFT\)）。
于是\((a-bi)\)的\(DFT\)可以通过\((a+bi)\)的\(DFT\)求。
所以只需要用\(4\)次\(DFT\)。

\(3.5\)次\(DFT\)？

抱歉这种高级算法不配我这种蒟蒻使用。
本蒟蒻也懒得学……
感兴趣的话可以看毛啸的论文。

瞎讲：任意模数MTT

原文：https://www.cnblogs.com/jz-597/p/12916178.html