NTT

用原根替换单位根做FTT，常用的质数是998244353，其最小原根为3；

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
const int mod = 998244353;
const int inv = 332748118;
ll qpow(ll a, ll b, ll mod){
	int m = 1;
	for(; b; b >>= 1){
		if(b & 1) m = (m * a) % mod;
		a = (a * a) % mod;
	}
	return m % mod;
}
int n, m, rev[4 * N];
ll a[4 * N], b[4 * N], c[4 * N];
void NTT(ll *a, int len, int type){
	int wei = 30 - __builtin_clz(len);
	for(int i = 0; i < len; i++){
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << wei); 
	}
	for(int i = 0; i < len; i++){
		if(rev[i] < i) swap(a[i], a[rev[i]]);
	}
	for(int k = 1; k * 2 <= len; k *= 2){
		ll w1;
		if(type == 1) w1 = qpow(3, (mod - 1) / (2 * k), mod);
		else w1 = qpow(inv, (mod - 1) / (2 * k), mod);
		for(int j = 0; j < len; j += k * 2){
			ll w2 = 1;
			for(int i = 0; i < k; i++){
				int f1 = a[j + i], f2 = a[j + i + k];
				a[j + i] = (f1 + (w2 * f2) % mod) % mod;
				a[j + i + k] = ((f1 - (w2 * f2) % mod) + mod) % mod;
				w2 = (w2 * w1) % mod;
			}
		}
	}
	if(type == -1){
		ll invlen = qpow(len, mod - 2, mod);
		for(int i = 0; i < len; i++){
			a[i] = (a[i] * invlen) % mod;
		}
	}
}
void dxstime(ll *a, ll n, ll *b, ll m, ll * c){
	int len = 1 << (1 + (int)log2(n + m - 1));
	NTT(a, len, 1);
	NTT(b, len, 1);
	for(int i = 0; i < len; i++) c[i] = (a[i] * b[i]) % mod;
	NTT(c, len, -1);
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 0; i <= n; i++) cin >> a[i];
	for(int i = 0; i <= m; i++) cin >> b[i];
	dxstime(a, n, b, m, c);
	for(int i = 0; i <= n + m; i++) cout << c[i] << " ";
	return 0;
}