BZOJ2194: 快速傅立叶之二(NTT,卷积)

#include<cstdio>
#define swap(x,y) x ^= y, y ^= x, x ^= y
#define LL long long 
using namespace std;
const int MAXN = 3 * 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();
    return x * f;
}
const int P = 998244353, g = 3, gi = 332748118;
int N;
int 
LL a[MAXN], b[MAXN], r[MAXN];
LL fastpow(LL a, int p, int mod) {
    LL base = 1;
    while(p) {
        if(p & 1) base = (base * a) % mod;
        a = (a * a) % mod; p >>= 1;
    }
    return base % mod;
}
LL NTT(LL *A, int type, int N, int mod) {
    for(int i = 0; i < N; i++) 
        if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < N; mid <<= 1) {
        LL W = fastpow( (type == 1) ? g : gi, (P - 1) / (mid << 1), mod ); 
        for(int j = 0; j < N; j += (mid << 1)) {
            int w = 1; 
            for(int k = 0; k < mid; k++, w = (w * W) % P) {
                LL x = A[j + k] % P, y = w * A[j + k + mid] % P;
                A[j + k] = (x + y) % P;
                A[j + k + mid] = (x - y + P) % P;
            } 
        }
    }
    if(type == -1) {
        LL inv = fastpow(N, mod - 2, mod);
        for(int i = 0; i < N; i++)
            A[i] = (A[i] * inv) % mod;
    }
}
int main() {
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    N = read();
    for(int i = 0; i < N; i++) 
        a[i] = read(), b[N - i] = read();
    int limit = 1, L = 0;
    while(limit <= N + N) limit <<=1, L++;
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
    NTT(a, 1, limit, P); NTT(b, 1, limit, P);
    for(int i = 0; i <  limit; i++) a[i] = (a[i] * b[i]) % P;
    NTT(a, -1, limit, P);
    for(int i = 0; i < N * 2; i++)
        printf("%d\n",a[i] % P);
    return 0;
}