代码

// Code by ajcxsu
// Problem: ntt

#define MOD (998244353)

void swap(int &x, int &y) { x^=y^=x^=y; }

int qpow(int x, int y) {
    // y=y%MOD+MOD-1;
    int ret=1;
    while(y) {
        if(y&1) ret=1ll*ret*x%MOD;
        x=1ll*x*x%MOD, y>>=1;
    }
    return ret;
}

const int N=4e6+10;
int a[N], b[N], r[N];
int n, m, l=0;
void fft(int x[], int y) {
    for(int i=1; i<n; i++) if(i<r[i]) swap(x[i], x[r[i]]);
    int t, o, w;
    for(int i=1; i<n; i<<=1) {
        o=qpow(3, y*(MOD-1)/(i<<1)+MOD-1);
        for(int j=0; j<n; j+=(i<<1)) {
            w=1;
            for(int k=0; k<i; k++, w=1ll*w*o%MOD)
                t=1ll*x[i+j+k]*w%MOD, (x[i+j+k]=x[j+k]-t+MOD)%=MOD, (x[j+k]+=t)%=MOD;
        }
    }
}

void poly_multiply(unsigned *A, int n, unsigned *B, int m, unsigned *C) {
    for(int i=0;i<=n;i++) a[i]=A[i];
    for(int i=0;i<=m;i++) b[i]=B[i];
    m+=n; for(n=1; n<=m; n<<=1) l++;
    for(int i=1;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    fft(a, 1), fft(b, 1); for(int i=0; i<n; i++) a[i]=1ll*a[i]*b[i]%MOD;
    int inv=qpow(n, MOD-2);
    fft(a, -1);
    for(int i=0;i<=m;i++) C[i]=1ll*a[i]*inv%MOD;
}

评测结果