Submission #421363

---

Source Code Expand

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

vector<complex<double> > dft(vector<complex<double> > f, int n, int dir) {
	if (n == 1) return f;
	vector<complex<double> > f0;
	vector<complex<double> > f1;
	for (int i = 0; i < n / 2; ++i) {
		f0.push_back(f[2 * i + 0]);
		f1.push_back(f[2 * i + 1]);
	}
	f0 = dft(f0, n / 2, dir);
	f1 = dft(f1, n / 2, dir);

	complex<double> zeta(cos(dir * 2 * 3.1415921535 / n), sin(dir * 2 * 3.1415921535 / n));
	complex<double> pow_zeta(1, 0);
	for (int i = 0; i < n; ++i) {
		f[i] = f0[i % (n / 2)] + pow_zeta * f1[i % (n / 2)];
		pow_zeta *= zeta;
	}
	return f;
}


vector<complex<double> > multiply(vector<complex<double> > g, vector<complex<double> > h) {
	int size = g.size() + h.size() + 1;
	int n;
	for (n = 1; n < size; n <<= 1) {
	}
	while(g.size() < n) g.push_back(complex<double>(0, 0));
	while(h.size() < n) h.push_back(complex<double>(0, 0));
	vector<complex<double> > gg = dft(g, n, 1);
	vector<complex<double> > hh = dft(h, n, 1);
	std::vector<complex<double> > ff;
	for (int i = 0; i < n; ++i) {
		ff.push_back(gg[i] * hh[i]);
	}
	ff = dft(ff, n, -1);
	for (int i = 0; i < ff.size(); ++i) {
		ff[i] /= n;
	}
	return ff;
}

int main(int argc, char const *argv[]) {
	int N;
	cin >> N;
	std::vector<complex<double> > A;
	std::vector<complex<double> > B;
	A.push_back(complex<double>(0, 0));
	B.push_back(complex<double>(0, 0));
	for (int i = 0; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		A.push_back(complex<double>(a, 0));
		B.push_back(complex<double>(b, 0));
	}
	/*
	std::vector<complex<double> > reta = dft(A, N);
	for (int i = 0; i < N; ++i) {
		cout << real(reta[i]) << " " << imag(reta[i]) << endl;
	}
	*/

	std::vector<complex<double> > ret = multiply(A, B);
	
	for (int i = 1; i <= 2 * N; ++i) {
		cout << (int)(real(ret[i]) + 0.1) << endl;
	}

	return 0;
}

Submission Info

Judge Result