代码

#include<bits/stdc++.h>
using namespace std;

#define il inline
#define mkp make_pair
#define pii pair<int,int>
#define lll __int128
#define ll long long
#define For(i,j,k) for(int i=(j); i<=(k); ++i)
#define ForDown(i,j,k) for(int i=(j); i>=(k); --i)
#define pb push_back
#define init(filename) freopen(filename ".in" ,"r",stdin);freopen(filename ".out" ,"w",stdout)
template<typename T> 
il void read(T &x){ x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args>
il void read(T &x, Args &... y){ read(x);read(y...); }

namespace NTT_algorithm
{
	static const int MAXN=3e6+5,g=3,ginv=332748118,mod=998244353;
	int rev[MAXN];
	il void change(ll *A, const int N)
	{
		For(i,0,N-1)
		{
			rev[i]=rev[i>>1]>>1;
			if(i&1) rev[i]|=N>>1;
		}
		For(i,0,N-1)
		{
			if(i<rev[i])
			{
				swap(A[i],A[rev[i]]);
			}
		}
	}
	il ll qpow(ll a, ll b)
	{
		ll ans=1;a%=mod;
		while(b)
		{
			if(b&1) (ans*=a)%=mod;
			(a*=a)%=mod;
			b>>=1;
		}
		return ans;
	}
	il void NTT(ll *A, const int N, const int tp)
	{
		change(A,N);
		for(int len=2; len<=N; len<<=1)
		{
			for(int i=0; i<N; i+=len)
			{
				ll G=qpow(tp==1?g:ginv,(mod-1)/len),cur=1,x,y;
				for(int j=i; j<i+(len>>1); j++)
				{
					x=A[j],y=A[j+(len>>1)]*cur%mod;
					A[j]=(x+y)%mod,A[j+(len>>1)]=(x+mod-y)%mod;
					(cur*=G)%=mod;
				}
			}
		}
	}
	il void mul(ll *A, ll *B, const int N, const int M, ll *R)
	{
		int len=1;
		while(len<=N+M) len<<=1;
		NTT(A,len,1);NTT(B,len,1);
		For(i,0,len-1) R[i]=A[i]*B[i]%mod;
		NTT(R,len,-1);
		ll inv=qpow(len,mod-2);
		For(i,0,N+M) (R[i]*=inv)%=mod;
	}
};

using NTT_algorithm::mul;

const int MAXN=3e6+5;
ll f[MAXN],g[MAXN],r[MAXN];

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
For(i, 0, n) f[i] = a[i];
For(i, 0, m) g[i] = b[i];
mul(f, g, n, m, r);
For(i, 0, n + m) c[i] = r[i];
}

评测结果