代码

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef int ll;
typedef long long int li;
typedef unsigned long long int ull;
const ll MAXN=262151,MOD=998244353,G=3,INVG=332748118;
ll fd,gd,cnt,limit;
ll f[MAXN],g[MAXN],res[MAXN],rev[MAXN],omgs[MAXN];
char buf[400051],*st=buf,*ed=buf;
inline char gc()
{
	return st==ed&&(ed=(st=buf)+fread(buf,1,400051,stdin),ed==st)?0:*st++; 
}
inline ll read()
{
    register ll num=0;
    register char ch=gc();
    while(!isdigit(ch))
    {
        ch=gc();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=gc();
    }
    return num;
}
inline void write(ll x)
{
	if(x>9)
	{
		write(x/10);
	}
	putchar(x%10+'0');
}
inline ll readSingleDigit()
{
    register char ch=gc();
    while(!isdigit(ch))
    {
        ch=gc();
    }
    if(isdigit(ch))
    {
        return ch-48;
    }
}
inline ll qpow(ll base,ll exponent)
{
    li res=1;
    while(exponent)
    {
        if(exponent&1)
        {
            res=1ll*res*base%MOD;
        }
        base=1ll*base*base%MOD,exponent>>=1;
    }
    return res;
}
inline void setupOmg(ll cnt)
{
	ll limit=log2(cnt)-1,omg;
	omg=qpow(G,(MOD-1)>>(limit+1)),omgs[cnt>>1]=1;
	for(register int i=(cnt>>1|1);i!=cnt;i++)
	{
		omgs[i]=(li)omgs[i-1]*omg%MOD;
	}
	for(register int i=(cnt>>1)-1;i;i--)
	{
		omgs[i]=omgs[i<<1]; 
	}
}
inline void NTT(ll *cp,ll cnt,ll inv)
{
	static ull tcp[MAXN];
    register ll cur=0,x,shift=log2(cnt)-__builtin_ctz(cnt);
    if(inv==-1)
    {
    	reverse(cp+1,cp+cnt);
	}
    for(register int i=0;i<cnt;i++)
	{
		tcp[rev[i]>>shift]=cp[i];
	}
    for(register int i=2;i<=cnt;i<<=1)
    {
        cur=i>>1;
        for(register int j=0;j<cnt;j+=i)
        {
            for(register int k=0;k<cur;k++)
            {
                x=tcp[j|k|cur]*omgs[k|cur]%MOD;
                tcp[j|k|cur]=tcp[j|k]+MOD-x,tcp[j|k]+=x;
            }
        }
    }
    for(register int i=0;i<cnt;i++)
    {
    	cp[i]=tcp[i]%MOD;
	}
	if(inv==1)
	{
		return;
	}
    x=MOD-(MOD-1)/cnt;
    for(register int i=0;i<cnt;i++)
    {
    	cp[i]=(li)cp[i]*x%MOD;
	}
}
int main()
{
	fd=read()+1,gd=read()+1;
	for(register int i=0;i<fd;i++)
	{
		f[i]=readSingleDigit();
	}
	for(register int i=0;i<gd;i++)
	{
		g[i]=readSingleDigit();
	}
	cnt=1,limit=-1;
	while(cnt<=(fd+gd))
	{
		cnt<<=1,limit++;
	}
	setupOmg(cnt);
	for(register int i=0;i<cnt;i++)
	{
		rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
	}
	NTT(f,cnt,1),NTT(g,cnt,1);
	for(register int i=0;i<cnt;i++)
	{
		f[i]=(li)f[i]*g[i]%MOD;
	}
	NTT(f,cnt,-1);
	for(register int i=0;i<fd+gd-1;i++)
	{
		write(f[i]),putchar(' ');
	}
}

评测结果