Submission #6898563

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define int long long
#define double long double
#define all(a) a.begin(), a.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

namespace FastFourierTransform{
    using Com = complex<double>;
    void DiscreteFourierTransform(vector<Com> &F, int inverse){
        int sz = (int)F.size(), half = sz / 2;
        if(sz == 1)return;
        vector<Com> former(half), latter(half);
        rep(i, half){
            former[i] = F[i << 1];
            latter[i] = F[i << 1 | 1];
        }
        DiscreteFourierTransform(former, inverse);
        DiscreteFourierTransform(latter, inverse);
        Com now = 1, sone = polar(1.0, inverse * 2 * acos(-1.0) / sz);
        rep(i, sz){
            F[i] = former[i & (half - 1)] + now * latter[i & (half - 1)];
            now *= sone;
        }
    }
    vector<int> Multiply(const vector<int>& A, const vector<int>& B){
        int sz = 1, newsize = (int)A.size() + (int)B.size() - 1;
        while(sz < newsize)sz <<= 1;
        vector<Com> F(sz), G(sz);
        rep(i, (int)A.size())F[i] = A[i];
        rep(i, (int)B.size())G[i] = B[i];
        DiscreteFourierTransform(F, 1);
        DiscreteFourierTransform(G, 1);
        rep(i, sz)F[i] *= G[i];
        DiscreteFourierTransform(F, -1);
        rep(i, sz)F[i] /= sz;
        vector<int> X(newsize);
        rep(i, newsize)X[i] = F[i].real() + 0.5;
        return X;
    }
};

signed main(void){

    int n; cin >> n;
    vector<int> a(n), b(n);
    rep(i, n)cin >> a[i] >> b[i];

    vector<int> c = FastFourierTransform::Multiply(a, b);
    cout << 0 << endl;
    for(int i : c)cout << i << endl;
    return 0;

}

Submission Info

Judge Result