Submission #1356910

---

Source Code Expand

#include<algorithm>
#include<cmath>
#include<complex>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"rprint.hpp"
#else
template <ostream& out = cout, class... T> void prints(T&&...){ }
template <ostream& out = cout, class... T> void printd(T&&...){ }
template <ostream& out = cout, class... T> void printb(T&&...){ }
template <ostream& out = cout, class... T> void printArr(T&&...){ }
#endif

using comp = complex<double>;

comp xi(int i, int n){
    return {cos(2 * M_PI * i / n), sin(2 * M_PI * i / n)};
}

auto dft(vector<comp>& cs, int n, bool rev = false, bool fin = false){
    vector<comp> ret(n);
    for(int i = 0; i < n; i++){
        comp acc = 1, x = xi((rev ? -i : i), n);
        for(auto c : cs){
            ret[i] += c * acc;
            acc *= x;
        }
        ret[i] /= (fin ? n : 1.0);
    }
    return ret;
}

vector<comp> fft(vector<comp>& cs, int n, bool rev = false, bool fin = false){
    vector<comp> ret(n), e, o;
    for(uint i = 0; i < cs.size(); i++){
        ((i & 1) ? o : e).push_back(cs[i]);
    }
    if(n == 1){
        ret[0] = cs.size() ? cs[0] : 0;
    }else{
        auto e2 = fft(e, n / 2, rev),
             o2 = fft(o, n / 2, rev);
        double den = fin ? n : 1;
        int revc = rev ? -1 : 1;
        for(int i = 0; i < n; i++){
            int idx = i % (n / 2);
            ret[i] = (e2[idx] + xi(revc * i, n) * o2[idx]) / den;
        }
    }
    return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<double> as(n), bs(n);
    vector<comp> gs(n), hs(n);
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        gs[i] = a;
        hs[i] = b;
    }
    int ceiln = 0;
    for(int i = 30; i >= 0; i--){
        if((2 * n + 1) & (1 << i)){
            ceiln = 1 << (i + 1);
            break;
        }
    }
    printd(ceiln);
    auto g2 = fft(gs, ceiln);
    auto h2 = fft(hs, ceiln);
    // auto g3 = dft(g2, ceiln, true);
    // auto h3 = dft(h2, ceiln, true);
    // printd(gs, g3);
    // printd(hs, h3);
    for(int i = 0; i < ceiln; i++){
        g2[i] = g2[i] * h2[i];
    }
    auto gh0 = fft(g2, ceiln, true, true);
    // prints(gh0);
    cout << 0 << '\n';
    for(int i = 0; i < 2 * n - 1; i++){
        cout << int(gh0[i].real() + 0.5) << '\n';
    }
    return 0;
}

Submission Info

Judge Result