MTT

合并$FFT$：三次翻转
一次：共轭单位根
两次：代入共轭单位根后的值需要再取共轭
三次：$A(x)+iB(x)$其中$A(x)=\frac{p-q}{2}$ ,则$B(x)=i\frac{q-p}{2}$。
任意模数多项式卷积：

#include<bits/stdc++.h>
#define maxn 300005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define db double
#define Ct const
#define Pi 3.1415926535897932384626433832795
using namespace std;

struct cp{
	db r,i;
	cp (Ct db &r=0,Ct db &i=0):r(r),i(i){}
	cp operator +(Ct cp &B)Ct{ return cp(r + B.r , i + B.i); }
	cp operator -(Ct cp &B)Ct{ return cp(r - B.r , i - B.i); }
	cp operator *(Ct cp &B)Ct{ return cp(r * B.r - i * B.i , i * B.r + r * B.i); }
	cp operator /(Ct db &B)Ct{ return cp(r / B , i / B); }
	cp conj()Ct{ return cp(r,-i); } 
}w[maxn];

int Wl,Wl2,lg[maxn];
void init(int n){
	for(Wl=1;n>=Wl<<1;Wl<<=1);Wl2 = Wl<<1;
	rep(i,0,Wl) w[i+Wl] = cp(cos(Pi*i/Wl) , sin(Pi*i/Wl));
	per(i,Wl-1,1) w[i] = w[i<<1];
	rep(i,2,Wl2) lg[i] = lg[i>>1]+1;
}
void FFT(cp *A,int n,int tp){
	static int r[maxn] = {};
	if(tp ^ 1) reverse(A+1,A+n);
	rep(i,0,n-1) i < (r[i] = r[i>>1] >> 1 | (i&1) << lg[n] - 1) && (swap(A[i],A[r[i]]) , 0);
	cp t;
	for(int L=1;L<n;L<<=1) for(int s=0,L2=L<<1;s<n;s+=L2) for(int k=s,x=L;k<s+L;k++,x++)
		t = w[x] * A[k+L] , A[k+L] = A[k] - t , A[k] = A[k] + t;
	if(tp ^ 1) rep(i,0,n-1) A[i] = A[i] / n;
}
void Mul(int *A,int *B,int *C,int n,int m,int cut = maxn,int mod = 1000000007){
	static int M = 32767; // 2 ^ 15 - 1
	static cp s[4][maxn];
	int L = 1 << lg[n + m] + 1;
	rep(i,0,L-1) 
		s[0][i] = cp(i <= n ? A[i] >> 15 : 0 , i <= m ? B[i] >> 15 : 0) ,
		s[1][i] = cp(i <= n ? A[i] & M : 0  , i <= m ? B[i] & M : 0);
	FFT(s[0],L,1) , FFT(s[1],L,1);
	rep(i,0,L-1){
		int v = (L-i) & (L-1);
		cp a[4] = {s[0][i] , s[0][v].conj() , s[1][i] , s[1][v].conj()};
		cp b[4] = {(a[0] + a[1]) * cp(0.5,0) , (a[1] - a[0]) * cp(0,0.5) , 
			(a[2] + a[3]) * cp(0.5,0) , (a[3] - a[2]) * cp(0,0.5)};
		s[2][i] = b[0] * b[1] + cp(0,1) * b[0] * b[3] , s[3][i] = b[2] * b[1] + cp(0,1) * b[2] * b[3];
	}	
	FFT(s[2],L,-1) , FFT(s[3],L,-1);
	rep(i,0,min(n+m,cut))
		C[i] = (
			(llround(s[2][i].r) % mod << 30)  
			+ ((llround(s[2][i].i) + llround(s[3][i].r)) % mod << 15)
			+ llround(s[3][i].i) ) % mod;
}