NTT：

void NTT(int *a,int type){
	for(int i=0;i<lim;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int k=1;k<lim;k<<=1){
		int wn=powmod(type==1?g:gi,(mod-1)/(k<<1));
		for(int i=0;i<lim;i+=(k<<1)){
			int w=1;
			for(int j=0;j<k;++j,w=1ll*w*wn%mod){
				int x=a[i+j],y=1ll*w*a[i+j+k]%mod;
				a[i+j]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
			}
		}
	}
	if(type==1)return ;
	int invn=powmod(lim,mod-2);
	for(int i=0;i<lim;++i){
		a[i]=1ll*a[i]*invn%mod;
	}
}

翻转数组：

lim=1,bit=0;
while(lim<=len*2)lim<<=1,bit+=1;
for(int i=0;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));