Submission #2628595

---

Source Code Expand

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

typedef long long ll;

#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)

typedef complex<double> Cdbl;

template<typename T>
inline void bit_reverse(vector<T>& a) {
    int n = a.size();
	int i = 0;
	for (int j=1; j<n-1; ++j) {
		for (int k = n >> 1; k >(i ^= k); k >>= 1);
		if (j < i) swap(a[i], a[j]);
	}
}

void dft(vector<Cdbl>& a, int sign=1){ // in-place
	const int n = a.size();
	assert((n ^ (n&-n)) == 0); //n = 2^k

    bit_reverse(a);

	for (int m=1; m<n; m<<=1) {
		const int m2 = 2 * m;
        // long long _base = mod_pow(h.val, n/m2, mod);
        double th = sign * M_PI * 2 / m2; // n * (n/m2); //(n/m2); //(n/m);
        // double th = sign * M_PI * 2 / (n/m2); //(n/m2); //(n/m);
        Cdbl _base(cos(th), sin(th)); // = mod_pow(h, n/m2, mod);
        Cdbl _w(1, 0);
		for (int x=0; x<m; ++x) {
			for (int s=x; s<n; s+=m2) {
				Cdbl u = a[s];
				Cdbl d = _w * a[s + m];
                a[s] = u+d;
                a[s+m] = u-d;
			}
            _w *= _base;
		}
	}
}
inline void idft(vector<Cdbl>& f) {
    dft(f, -1);
    int n = f.size();
    rep(i, n) f[i] /= n;
}

vector<Cdbl> convolution_dft(vector<Cdbl>& g, vector<Cdbl>& h) {
    int result_size = g.size() + h.size() - 1;
    int n = 1; while (n < result_size) n <<= 1;

    g.resize(n, 0);
    h.resize(n, 0);

    dft(g);
    dft(h);
    vector<Cdbl> f(n, 0);
    for (int i=0; i<n; ++i) f[i] = g[i] * h[i];
    idft(f);

    f.resize(result_size);
    return f;
}

vector<ll> convolution_dft_ll(vector<ll>& g, vector<ll>& h) {
    vector<Cdbl> _g(g.size()), _h(h.size());
    rep(i, g.size()) _g[i] = g[i];
    rep(i, h.size()) _h[i] = h[i];

    vector<Cdbl> _f = convolution_dft(_g, _h);
    vector<ll> f(_f.size());
    rep(i, _f.size()) f[i] = (ll)round(_f[i].real());
    return f;
}


int main() {
    int N; cin >> N; // 1-100000

    vector<ll> g(N+1), h(N+1);

    g[0] = h[0] = 0;
    rep(i,N){
        int A,B; cin >> A >> B;
        g[1+i] = A;
        h[1+i] = B;
    }

    vector<ll> f = convolution_dft_ll(g, h);

    rep1(k, N*2){
        cout << f[k] << endl;
    }

    return 0;
}

Submission Info

Judge Result