Submission #422031

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
#include <complex>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;

const int INF = 1e9;
const int MOD = 1e9+7;

typedef complex<double> Comp;
typedef vector<Comp> vc;
vc fft(vc f, bool inv = false){
    int n = f.size();
    if(n == 1) return f;
    vc f0, f1;
    REP(i, n / 2) f0.push_back(f[2 * i + 0]);
    REP(i, n / 2) f1.push_back(f[2 * i + 1]);
    f0 = fft(f0, inv); f1 = fft(f1, inv);
    double deg = (inv ? -1 : 1) * 2 * M_PI / n;
    Comp zeta = Comp(cos(deg), sin(deg));
    Comp pow_zeta = Comp(1.0, 0.0);
    REP(i, n){
        f[i] = f0[i % (n / 2)] + pow_zeta * f1[i % (n / 2)];
        pow_zeta *= zeta;
    }
    return f;
}
vc multiply(vc g, vc h){
    int n = 1;
    while(n < g.size() + h.size() + 1) n<<=1;
    while(g.size() < n) g.push_back(Comp(0.0, 0.0));
    while(h.size() < n) h.push_back(Comp(0.0, 0.0));
    vc gg = fft(g);
    vc hh = fft(h);
    REP(i, n) gg[i] *= hh[i];
    gg = fft(gg, true);
    REP(i, n) gg[i] /= n;
    return gg;
}

int main(void){
    int N;
    cin >> N;
    vc A(N+1), B(N+1);
    REP(i, N){
        double x, y;
        cin >> x >> y;
        A[i+1] = Comp(x, 0);
        B[i+1] = Comp(y, 0);
    }
    vc cc = multiply(A, B);
    REP(i, 2 * N + 1){
        if(!i) continue;
        cout << (ll)(real(cc[i]) + 0.01) << endl;   
    }

    return 0;
}

Submission Info

Judge Result