NTT总结

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132591415

https://www.luogu.com.cn/problem/P3803

公式：

$$\large\omega_n^1\equiv g^{\frac {p-1}n}\pmod p$$

然后所有单位根运算都可以转成原根了！（前提 $p$ 为质数）

$p$ 常为 998244353，它的原根 $g$ 为 3

实现细节：

1. IDFT时 $g$ 要取逆元 $-g=g^{-1}=\frac g p$ （可以把 $g$ 看成单位根然后在单位圆上理解）

2. 最后除 $n$ 要变成乘上 $n$ 的逆元

3. 当 $p=99824435$ 时， $p-1=998244352=2^{23}\times 7\times 17$ ，所以可以直接除，此步不用取逆元

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define M
#define mo 998244353
#define N 3000010
#define G 3
int n, m, i, j, k, T;
int a[N], b[N], r[N], l; 

int pw(int a, int b) {
	int ans=1; 
	while(b) {
		if(b&1) ans*=a; 
		b>>=1; a*=a; 
		ans%=mo; a%=mo; 
	}
	return ans; 
}

const int invG=pw(G, mo-2); 

void NTT(int *P, int op) {
	for(i=0; i<n; ++i) if(i<r[i]) swap(P[i], P[r[i]]); 
	for(i=1; i<n; i<<=1) {
		int W=pw(op==1 ? G : invG, (mo-1)/(i<<1)); //改动！
		for(j=0; j<n; j+=(i<<1)) {
			int w=1; 
			for(k=0; k<i; ++k, w=w*W%mo) { 
				int X=P[j+k], Y=w*P[j+k+i]%mo; 
				P[j+k]=(X+Y)%mo; P[j+k+i]=(X-Y+mo)%mo;
			}
		}
	}
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=0; i<=n; ++i) a[i]=read(); 
	for(i=0; i<=m; ++i) b[i]=read(); 
	m+=n; 
	for(n=1; n<=m; n<<=1) ++l; 
	for(i=0; i<n; ++i) r[i]=((r[i>>1]>>1)|((i&1)<<l-1)); 
	NTT(a, 1); NTT(b, 1);  
	for(i=0; i<n; ++i) a[i]*=b[i], a[i]%=mo; 
	NTT(a, -1); 
	k=pw(n, mo-2); 
	for(i=0; i<=m; ++i) printf("%lld ", a[i]*k%mo); 
	
	return 0;
}