代码

#define DREP(i, s, e) for(int i(s), end_##i(e); i >= end_##i ;i--)
#define  REP(i, s, e) for(int i(s), end_##i(e); i <= end_##i ;i++)

#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)

#include <iostream>
#include <cstdio>
using namespace std;
const int maxlen = (1e5 + 1e5 + 10) * 2, MOD = 998244353;

char buf[maxlen + 5], *p = buf;
#define Getchar() (*p++)

int power_pow(long long base, int b)
{
	long long ans(1);
	while (b)
	{
		if (b & 1) (ans *= base) %= MOD;
		(base *= base) %= MOD;
		b >>= 1;
	}
	return ans;
}
#define inv(x) power_pow(x, MOD - 2)

int n, m, k;

inline void write(int x) {if (x / 10) write(x / 10);putchar(x % 10 + '0');}

int L, len, *R, *f, *g;
inline void NTT(int a[], int flag)
{
	REP(i, 1, len - 1)
		if (i < R[i]) swap(a[i], a[R[i]]);
	for (int i = 1; i < len; i <<= 1)
	{
		int wn = power_pow(3, (MOD - 1) / (i << 1));
		if (flag < 0) wn = inv(wn);
		for (int k = 0; k < len; k += i << 1)
		{
			long long w(1);
			for (int l(0); l < i; l++, (w *= wn) %= MOD)
			{
				int x(a[k + l]), y(w * a[k + l + i] % MOD);
				a[k + l] = (x + y) % MOD;
				a[k + l + i] = (x - y) % MOD;
			}
		}
	}
	if (flag < 0)
	{
		static const int invN = inv(len);
		REP(i, 0, len - 1) a[i] = 1ll * a[i] * invN % MOD;
	}
}

signed main()
{
#ifdef CraZYali
	freopen("NTT.in", "r", stdin);
	freopen("NTT.out", "w", stdout);
#endif
	fread(buf, 1, maxlen, stdin);
	char c;
	while (isdigit(c = Getchar())) n = n * 10 + c - 48;
	while (isdigit(c = Getchar())) m = m * 10 + c - 48;
	L = 1;
	while ((1 << L) <= n + m) L++;
	len = 1 << L;
	R = new int[len];R[0] = 0;
	f = new int[len];
	g = new int[len];
	REP(i, 1, len - 1) R[i] = (R[i >> 1] >> 1) | ((i & 1) << L-1);
	REP(i, 0, n) f[i] = Getchar() - 48, Getchar();
	REP(i, 0, m) g[i] = Getchar() - 48, Getchar();
	REP(i, n + 1, len - 1) f[i] = 0 ;
	REP(i, m + 1, len - 1) g[i] = 0 ;
	NTT(f, 1);NTT(g, 1);
	REP(i, 0, len-1) f[i] = 1ll * f[i] * g[i] % MOD;
	NTT(f, -1);
	REP(i, 0, n + m) write((f[i] + MOD) % MOD), putchar(' ');
	return 0;
}

评测结果