代码

#include <bits/stdc++.h>
#define Pb push_back
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 3e5 + 7, Mod = 998244353;
inline int R() { int rt; scanf ( "%d", &rt ); return rt; }
ll Pow ( ll bs, int t ) { int rt = 1; for ( ; t; t >>= 1, bs = bs * bs % Mod ) if ( t & 1 ) rt = rt * bs % Mod; return rt; }
inline int Mop ( int na ) { return na >= Mod ? na - Mod : na; }

int pos[MAXN];
void Pre ( int sz )
{
	int lm = 0;
	for ( ; ( 1 << lm ) < sz; ++lm );
	for ( int i = 0; i < sz; ++i ) { pos[i] = pos[i >> 1] >> 1; if ( i & 1 ) pos[i] |= 1 << lm - 1; }
}

ll a[MAXN], b[MAXN], w[MAXN];
void Gao ( ll *t, int sz, int tp )
{
	for ( int i = 0; i < sz; ++i ) if ( pos[i] < i ) swap ( t[i], t[pos[i]] );
	for ( int nl = 2; nl <= sz; nl <<= 1 )
	{
		int hl = nl >> 1;
		w[0] = 1, w[1] = Pow ( 3, ( Mod - 1 ) / nl );
		if ( tp == -1 ) w[1] = Pow ( w[1], Mod - 2 );
		for ( int i = 2; i < hl; ++i ) w[i] = w[i - 1] * w[1] % Mod;
		for ( int sp = 0; sp < sz; sp += nl )
			for ( int i = sp; i < sp + hl; ++i )
			{
				ll temp = t[i + hl] * w[i - sp] % Mod;
				t[i + hl] = Mop ( t[i] + Mod - temp );
				t[i] = Mop ( t[i] + temp );
			}
	}
	if ( tp == -1 ) { ll rv = Pow ( sz, Mod - 2 ); for ( int i = 0; i < sz; ++i ) t[i] = t[i] * rv % Mod; }
}

int main()
{
	int n = R(), m = R(), ms = 1;
	for ( ; ms < n + m + 1; ms <<= 1 );
	for ( int i = 0; i <= n; ++i ) a[i] = R();
	for ( int i = 0; i <= m; ++i ) b[i] = R();
	Pre ( ms ), Gao ( a, ms, 1 ), Gao ( b, ms, 1 );
	for ( int i = 0; i < ms; ++i ) a[i] = a[i] * b[i] % Mod;
	Gao ( a, ms, -1 );
	for ( int i = 0; i < n + m + 1; ++i ) printf ( "%lld ", a[i] );
	return 0;
}

评测结果