SPOJ Polynomial Multiplication / Fast Fourier transform

/***
 created: 2022-08-14-23.16.33
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'
#define PI acos(-1.0)
typedef complex<double> base;

void fft(vector<base> & a, bool invert) {
    int n = (int)a.size();

    for (int i = 1, j = 0; i<n; ++i) {
        int bit = n >> 1;
        for (; j >= bit; bit >>= 1)j -= bit;
        j += bit;
        if (i < j)swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        base wlen(cos(ang), sin(ang));
        for (int i = 0; i<n; i += len) {
            base w(1);
            for (int j = 0; j<len / 2; ++j) {
                base u = a[i + j], v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert)for (int i = 0; i<n; ++i)a[i] /= n;
}
vector<ll> Mul(vector<ll>& a, vector<ll>& b)
{
    vector<base> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < max(a.size(), b.size()))  n <<= 1;
    n <<= 1;
    fa.resize(n), fb.resize(n);

    fft(fa, false), fft(fb, false);
    for (int i = 0; i<n; ++i)fa[i] *= fb[i];
    fft(fa, true);

    vector<ll> res;
    res.resize(n);
    for (int i = 0; i<n; ++i)res[i] = round(fa[i].real());

//  int carry=0;
//
//  for(int i=0;i<n;i++)
//    {
//        res[i]+=carry;
//        carry=res[i]/10;
//        res[i]%=10;
//    }

    while(res.size()>1 && res.back()==0)
    {
        res.pop_back();
    }

    //reverse(res.begin(),res.end());

    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    test
    {
        ll i,n,m,j,k,l;

        vector<ll>x,y,ans;

        cin>>n;

        for(i=0;i<=n;i++)
        {
            cin>>m;
            x.push_back(m);
        }

        for(i=0;i<=n;i++)
        {
            cin>>m;
            y.push_back(m);
        }

        reverse(x.begin(),x.end());
        reverse(y.begin(),y.end());

        ans=Mul(x,y);

        for(i=ans.size()-1;i>=0;i--)
        {
            cout<<ans[i]<<" ";
        }

        cout<<nl;

    }

    get_lost_idiot;
}