代码

#include <iostream>
#include <math.h>
#include <string.h>
#include <algorithm>
typedef long long LL;
const int MAXC = 7e6;
const int MAXN = 3e5;
const int MOD = 998244353;
const int G = 3;

int fastPow(LL b, int p) {
    int ret = 1;

    while (p) {
        if (p & 1) ret = ret % MOD * b % MOD;
        b = b % MOD * b % MOD;
          
        p >>= 1;
    }
  
    return ret % MOD;
}

int inv(int x) {
    return (fastPow(x, MOD - 2) + MOD) % MOD;
}

int N;

struct NumberTheoreticTransform {
    int omega[MAXN + 5], omegaInverse[MAXN + 5];
    int r[MAXN + 5], k;

    NumberTheoreticTransform() : k(0) {
        memset(r, 0, sizeof(r));
    }

    void init() {
        LL x = fastPow(G, (MOD - 1) / N);
        
        omega[0] = omegaInverse[0] = 1;
        for (int i = 1; i < N; ++i)
            omega[i] = omegaInverse[N - i] = omega[i - 1] * x % MOD;
        
        while ((1 << k) < N) 
            ++k;

        for (int i = 0; i < N; ++i) 
            r[i] = (r[i >> 1] >> 1) | ((i & 1) << (k - 1)); 
    }

    void operator()(unsigned *a, const int type) {
        for (int i = 0; i < N; ++i)
            if (i < r[i]) swap(a[i], a[r[i]]);

        for (int l = 2; l <= N; l <<= 1) {
            int m = l >> 1;

            for (int p = 0; p < N; p += l) 
                for (int i = 0; i < m; ++i) {
                    LL t = (type == 1 ? omega[N / l * i] : omegaInverse[N / l * i]) * a[p + i + m] % MOD;
                    a[p + i + m] = (a[p + i] - t + MOD) % MOD;
                    a[p + i] = (a[p + i] + t) % MOD;
                }
        }
        
        if (type == -1) {
            int x = inv(N);
            for (int i = 0; i < N; ++i)
                a[i] = a[i] * x % MOD;
        }
    }
}NTT;

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
    ++n;
    ++m;

    N = 1;
    while (N <= n + m)
        N <<= 1;
    NTT.init();

    NTT(a, 1);
    NTT(b, 1);
    for (int i = 0; i < N; ++i)
        a[i] = LL(a[i] % MOD * a[i]) % MOD;
    
    NTT(a, -1);
    for (int i = 0; i < n + m - 1; ++i)
        c[i] = a[i];
}

评测结果