代码

#include<bits/stdc++.h>
using namespace std;
namespace jly{
constexpr int P = 998244353;

int power(int a, int b) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % P) {
        if (b % 2) {
            res = 1LL * res * a % P;
        }
    }
    return res;
}
namespace AllVec{
std::vector<int> rev, roots {0, 1};


void dft(std::vector<int> &a) {
    int n = a.size();
    if (int(rev.size()) != n) {
        int k = __builtin_ctz(n) - 1;
        rev.resize(n);
        for (int i = 0; i < n; i++) {
            rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
        }
    }
    for (int i = 0; i < n; i++) {
        if (rev[i] < i) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    if (roots.size() < n) {
        int k = __builtin_ctz(roots.size());
        roots.resize(n);
        while ((1 << k) < n) {
            int e = power(31, 1 << (__builtin_ctz(P - 1) - k - 1));
            for (int i = 1 << (k - 1); i < (1 << k); i++) {
                roots[2 * i] = roots[i];
                roots[2 * i + 1] = 1LL * roots[i] * e % P;
            }
            k++;
        }
    }

    for (int k = 1; k < n; k *= 2) {
        for (int i = 0; i < n; i += 2 * k) {
            for (int j = 0; j < k; j++) {
                int u = a[i + j];
                int v = 1LL * a[i + j + k] * roots[k + j] % P;
                a[i + j] = (u + v) % P;
                a[i + j + k] = (u +P- v) % P;
            }
        }
    }
}

void idft(std::vector<int> &a) {
    int n = a.size();
    std::reverse(a.begin() + 1, a.end());
    dft(a);
    int inv = (1 - P) / n+P;
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * inv % P;
    }
}

std::vector<int> mul(std::vector<int> a, std::vector<int> b) {
    int n = 1, tot = a.size() + b.size() - 1;
    while (n < tot) {
        n *= 2;
    }
    if (tot < 128) {
        std::vector<int> c(a.size() + b.size() - 1);
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                c[i + j] = (c[i + j] + 1LL * a[i] * b[j]) % P;
            }
        }
        return c;
    }
    a.resize(n);
    b.resize(n);
    dft(a);
    dft(b);
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * b[i] % P;
    }
    idft(a);
    a.resize(tot);
    return a;
}

}
const int MAXBITLEN=21;
int curn,alrn=2,rev[1<<MAXBITLEN|7],roots[1<<MAXBITLEN|7]={0,1};
template<class InputIt>
void dft(InputIt first,InputIt last) {
    int n = last-first;
    if (curn != n) {
        int k = __builtin_ctz(n) - 1;
        curn=n;
        for (int i = 0; i < n; i++) {
            rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
        }
    }
    for (int i = 0; i < n; i++) {
        if (rev[i] < i) {
            std::swap(first[i], first[rev[i]]);
        }
    }
    if (alrn < n) {
        int k = __builtin_ctz(alrn);
        alrn=n;
        while ((1 << k) < n) {
            int e = power(31, 1 << (__builtin_ctz(P - 1) - k - 1));
            for (int i = 1 << (k - 1); i < (1 << k); i++) {
                roots[2 * i] = roots[i];
                roots[2 * i + 1] = 1LL * roots[i] * e % P;
            }
            k++;
        }
    }

    for (int k = 1; k < n; k *= 2) {
        for (int i = 0; i < n; i += 2 * k) {
            for (int j = 0; j < k; j++) {
                int u = first[i + j];
                int v = 1LL * first[i + j + k] * roots[k + j] % P;
                first[i + j] = (u + v)>=P?(u+v-P):(u+v);
                first[i + j + k] = (u>=v)?(u-v):(u+P-v);
            }
        }
    }
}
template<class InputIt>
void idft(InputIt first,InputIt last) {
    int n = last-first;
    std::reverse(first + 1, last);
    dft(first,last);;
    int inv = (1 - P) / n+P;
    for (int i = 0; i < n; i++) {
        first[i] = 1LL * first[i] * inv % P;
    }
}

template<class InputIt,class OutputIt>
OutputIt mul(InputIt afirst,InputIt alast,InputIt bfirst,InputIt blast,OutputIt dfirst){
	static int a[1<<MAXBITLEN|7],b[1<<MAXBITLEN|7];
	std::copy(afirst,alast,a);std::copy(bfirst,blast,b);
    int n = 1, tot = alast-afirst + blast-bfirst - 1;
    auto dlast=dfirst+tot;
    while (n < tot) {
        n *= 2;
    }
    if (tot < 128) {
//        std::vector<int> c(a.size() + b.size() - 1);
        for (auto i = 0; i < alast-afirst; i++) {
            for (int j = 0; j < blast-bfirst; j++) {
                dfirst[i + j] = (dfirst[i + j] + 1LL * afirst[i] * bfirst[j]) % P;
            }
        }
        return dlast;
    }
    std::fill(a+(alast-afirst),a+n,0);
    std::fill(b+(blast-bfirst),b+n,0);
    dft(a,a+n);
    dft(b,b+n);
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * b[i] % P;
    }
    idft(a,a+n);
    std::copy(a,a+tot,dfirst);
    return dlast;
}
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c){
	jly::mul(a,a+n+1,b,b+m+1,c);
}

评测结果