polymul.cpp

#include <bits/stdc++.h>
#define NMAX 100006
using namespace std;

typedef complex<double> Complex;
typedef valarray<Complex> CArray;

const double pi = acos(-1);
int test, n, next_power_2;
Complex a[NMAX], b[NMAX], z;
CArray A, B;

void fft(CArray &X, int N, bool inv) {

    if(N <= 1)
        return ;

    Complex w = 1, wn = polar(1.0, 2*pi/N);
    if(inv)
        wn = polar(1.0, -2*pi/N);

    CArray even = X[slice(0, N/2, 2)], odd = X[slice(1, N/2, 2)];

    fft(even, N/2, inv);
    fft(odd, N/2, inv);

    for(size_t k=0;k<N/2;k++) {
        z = w*odd[k];
        X[k] = even[k] + z;
        X[k+N/2] = even[k] - z;
        w *= wn;
    }
}

void poly_mul(CArray &X, CArray &Y, int N, bool inv) {
    fft(X, N, inv);
    fft(Y, N, inv);

    X *= Y;

    fft(X, N, !inv);
    X /= N;
}

void solve() {

    scanf("%d",&n);
    n += 1;

    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));

    for(size_t i=0;i<n;i++)
        scanf("%lf",&a[i]);
    for(size_t j=0;j<n;j++)
        scanf("%lf",&b[j]);

    next_power_2 = 1;
    while(next_power_2 < n)
        next_power_2 <<= 1;

    A = CArray(a, 2*next_power_2);
    B = CArray(b, 2*next_power_2);

    poly_mul(A, B, 2*next_power_2, false);

    for(size_t i=0;i<2*n-1;i++)
        printf("%.0f ",real(A[i]));
    printf("\n");

}

int main() {

    scanf("%d",&test);

    while(test--)
        solve();

    return 0;
}