代码

// with IO of https://uoj.ac/submission/157997

#include <cstdio>
#include <cctype>
#include <algorithm>

struct buf{
	char a[1<<25],*s;
	char b[1<<25],*t;
	buf():s(a),t(b){a[fread(a,1,sizeof a,stdin)]=0;}
	~buf(){fwrite(b,1,t-b,stdout);}
	operator int(){
		int x=0;
		while(*s<48)++s;
		while(*s>32)
			x=x*10+*s++-48;
		return x;
	}
	void out(int x){
		static char c[12];
		char*i=c;
		if(!x)*t++=48;
		else{
			while(x){
				int y=x/10;
				*i++=x-y*10+48,x=y;
			}
			while(i!=c)*t++=*--i;
		}
		*t++=32;
	}
}it;

const int N =     1 << 21;
const int p =    81 << 21 | 1;
const int g =  1167 << 12 | 1;
const int h = 11443 << 12 | 1;

inline int pow_modp(int a, int b) { int x = 1; for(; b; a = (long long)a * a % p, b >>= 1) if(b & 1) x = (long long)x * a % p; return x; }

int ntt_sup[N];
inline void ntt(auto a[], int n, const int g) {
	auto b = ntt_sup, j = a, _j = a; int _n = n >> 1, i, k, _k, w, _w;
	for(i = 1, w = pow_modp(g, (p - 1) / n); i < n; i <<= 1, w = (long long)w * w % p, std :: swap(a, b))
		for(k = 0, j = a, _j = a + _n, _w = 1; k != n; k += i, _w = (long long)_w * w % p)
			for(_k = k, k += i; _k != k; ++j, ++_j, ++_k)
				b[_k] = *j + *_j < 0 ? *j + *_j + p : *j + *_j - p,
				b[_k + i] = (long long)(*j - *_j) * _w % p;
	if(b != ntt_sup) std :: copy(a, a + n, b);
}
inline void poly_mul(auto a[], auto b[], int n) {
	ntt(a, n, g), ntt(b, n, g);     for(int i = 0; i < n; ++i) a[i] = (long long)a[i] * b[i] % p; ntt(a, n, h);
	int inv_n = pow_modp(n, p - 2); for(int i = 0; i < n; ++i) a[i] = (long long)a[i] * inv_n % p;
	for(int i = 0; i < n; ++i) a[i] = a[i] < 0 ? a[i] + p : a[i];
}

int n, n_a, n_b;
int a[N], b[N];

int main(void) {
	n_a = it, n_b = it; for(n = 1; n <= n_a + n_b; n <<= 1);
	for(int i = 0; i <= n_a; ++i) a[i] = it;
	for(int i = 0; i <= n_b; ++i) b[i] = it;
	poly_mul(a, b, n);
	for(int i = 0 ; i <= n_a + n_b; ++i) it.out(a[i]);
	return 0;
}

评测结果