rt 2.89s 跑不过 FFT

#include<bits/stdc++.h>
#define ll long long
#define N 2000005
using namespace std;
const int G=3,iG=332748118;
const ll mod=998244353;
int Qpow(int a,int x)
{
	int s=1;
	while(x)
	{
		if(x&1) s=1ll*s*a%mod;
		a=1ll*a*a%mod;
		x>>=1;
	}
	return s;
}
int n,m;
int f[N*2],g[N*2];
int tr[N*2];
void NTT(int *f,int n,bool flag)
{
	for(int i=0;i<n;i++)
		if(i>tr[i]) swap(f[i],f[tr[i]]);
	for(int k=2;k<=n;k<<=1)
	{
		int len=(k>>1);
		int cur,w=Qpow(flag?G:iG,(mod-1)/k);
		for(int j=0;j<n;j+=k)
		{
			cur=1;
			for(int i=j;i<j+len;i++)
			{
				int tmp=1ll*cur*f[i+len]%mod;
				f[i+len]=f[i]-tmp;
				f[i]=f[i]+tmp;
				if(f[i+len]<0) f[i+len]+=mod;
				if(f[i]>mod) f[i]-=mod;
				cur=1ll*cur*w%mod;
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++) scanf("%d",&f[i]);
	for(int i=0;i<=m;i++) scanf("%d",&g[i]);
	for(m=n+m+1,n=1;n<m;n<<=1);
	for(int i=1;i<n;i++)
		tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,1),NTT(g,n,1);
	for(int i=0;i<n;i++) f[i]=1ll*f[i]*g[i]%mod;
	NTT(f,n,0);
	int invn=Qpow(n,mod-2);
	for(int i=0;i<m;i++) printf("%d ",1ll*f[i]*invn%mod);
	return 0;
}

试了一下三目运算，快读，预处理原根次方，效果都不佳

是不是假了 qwq