代码

/**********************************************************
 * By Jerry Zheng
 * 
 * Get more points as possible.
 * Is the understanding of the statement correct?
 * If Subtask #2 is too hard, why not try Subtask #3?
 * 
 * Think twice, code once.
 * Are there any counterexamples to your algo?
 * Is the sol too heavy to debug?
 * Is the Time & Meomry complexity correct?
 * 
 * DON'T MAKE STUPID MISTAKES!!!!!
 * file-IO? DEBUG output? array size?
 * boundaries? long long?
 *
                         _ooOoo_
                        o8888888o
                        88" . "88
                        (| -_- |)
                        O\  =  /O
                     ____/`---'\____
                   .'  \|     |//  `.
                  /  \|||  :  |||//  \
                 /  _||||| -:- |||||-  \
                 |   | \  -  /// |   |
                 | \_|  ''\---/''  |   |
                 \  .-\__  `-`  ___/-. /
               ___`. .'  /--.--\  `. . __
            ."" '<  `.___\_<|>_/___.'  >'"".
           | | :  `- \`.;`\ _ /`;.`/ - ` : | |
           \  \ `-.   \_ __\ /__ _/   .-` /  /
      ======`-.____`-.___\_____/___.-`____.-'======
                         `=---='
      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                 佛祖保佑        永无BUG
**********************************************************/
#include <bits/stdc++.h>

#define IL inline
#define CT const
#define RG register
#define TT template <typename Ty>

namespace io {
const int MaxBuff = 1 << 15, MaxOut = 1 << 24;
char b[MaxBuff], *S = b, *T = b, buff[MaxOut], *iter = buff;
FILE *_IN = stdin, *_OUT = stdout;
IL char gc() { return S == T && (T = (S = b) + fread(b, 1, MaxBuff, _IN), S == T) ? 0 : *S++; }
IL void ps(const char *s) { while (*s) *iter++ = *s++; }
IL void pc(const char s) { *iter++ = s; }
IL void fflush() { fwrite(buff, 1, iter - buff, _OUT), iter = buff, fclose(_IN), fclose(_OUT); }
} // namespace io

TT IL Ty max(CT Ty& a, CT Ty& b) { return a > b ? a : b; }
TT IL Ty min(CT Ty& a, CT Ty& b) { return a < b ? a : b; }
TT IL void cmax(Ty& a, CT Ty& b) { if (b > a) a = b; }
TT IL void cmin(Ty& a, CT Ty& b) { if (b < a) a = b; }
TT IL void swap(Ty& a, Ty& b) { Ty t = a; a = b; b = t; }
TT IL void swap(Ty*& a, Ty*& b) { Ty *t = a; a = b; b = t; }

TT IL void read(Ty& t) {
	t = 0; int f = 1; RG char ch = io::gc();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = io::gc(); }
	do { t = t * 10 + ch - '0'; ch = io::gc(); } while (ch >= '0' && ch <= '9'); t *= f;
}

TT IL void write(Ty x) {
	if (x < 0) io::pc('-');
	if (x > 9) write(x / 10);
	io::pc(x % 10 + '0');
}

const int N = 2e6 + 5;
const int wcz = 998244353;

namespace poly {
typedef long long ll;

IL int qpow(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1, a = ((ll)a * a) % wcz)
        if (b & 1)
            ans = ((ll)ans * a) % wcz;
    return ans;
}

int n, rev[N * 4], w[N * 4], inv_w[N * 4];

void ntt(int *a) {
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int step = 1, ws = n / 2; step < n; step *= 2, ws /= 2)
        for (int j = 0; j < n; j += step * 2)
            for (int k = j, wn = 0; k < j + step; ++k, wn += ws) {
                int x = a[k], y = ((ll)a[k + step] * w[wn]) % wcz;
                a[k] = (x + y) % wcz, a[k + step] = (x - y + wcz) % wcz;
            }
}

void intt(int* a) {
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int step = 1, ws = n / 2; step < n; step *= 2, ws /= 2)
        for (int j = 0; j < n; j += step * 2)
            for (int k = j, wn = 0; k < j + step; ++k, wn += ws) {
                int x = a[k], y = ((ll)a[k + step] * inv_w[wn]) % wcz;
                a[k] = (x + y) % wcz, a[k + step] = (x - y + wcz) % wcz;
            }
    for (int i = 0, inv = qpow(n, wcz - 2); i < n; i++)
        a[i] = ((ll)a[i] * inv) % wcz;
}

IL void init_n(int nn) {
    for (n = 1; n <= nn; n <<= 1) ;
    for (int i = 0; i < n; ++i)
        rev[i] = (i & 1) ? (rev[i - 1] + n / 2) : (rev[i / 2] / 2);
    int gn = qpow(3, (wcz - 1) / n), gm = qpow(gn, wcz - 2);
    for (int i = 0, j1 = 1, j2 = 1; i < n; ++i)
        w[i] = j1, j1 = ((ll)j1 * gn) % wcz, inv_w[i] = j2,
        j2 = ((ll)j2 * gm) % wcz;
}
} // namespace poly

int n, m, a[N * 4], b[N * 4];
char s[2000005];

int main() {
	read(n), read(m);
	for (int i = 0; i <= n; ++i) read(a[i]);
	for (int i = 0; i <= m; ++i) read(b[i]);
    poly::init_n(n + m + 1);
    poly::ntt(a), poly::ntt(b);
    for (int i = 0; i < poly::n; ++i) a[i] = ((long long)a[i] * b[i]) % wcz;
    poly::intt(a);
    int flag = 1;
    for (int i = 0; i < n + m + 1; ++i) write(a[i]), io::pc(' ');
    io::pc('\n');
    io::fflush();
    return 0;
}

评测结果