Submission #421738


Source Code Expand

#include<iostream>
#include<complex>
#include<cmath>
#include<vector>
#include<algorithm>
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,n) for(int (i)=0;i<int(n);i++)
using  namespace std;

typedef long double Real;
typedef complex<Real> Complex;
Real const PI=acos(-1);
namespace FFT{
	vector<Complex> FFT(vector<Complex>& f,int inv=0){
		int n=f.size();
		if(n==1) return f;
		vector<Complex> f0(n/2);
		vector<Complex> f1(n/2);
		REP(i,n/2) f0[i]=f[2*i],f1[i]=f[2*i+1];
		f0=FFT(f0,inv); f1=FFT(f1,inv);
		if (inv) REP(i,n) f[i]=f0[i%(n/2)] + polar<Real>(1,-2*PI/n*i)*f1[i%(n/2)];
		else     REP(i,n) f[i]=f0[i%(n/2)] + polar<Real>(1, 2*PI/n*i)*f1[i%(n/2)];
		return f;

	}
	vector<Complex> convolution(vector<Complex> g,vector<Complex> h){
		int n_=max(g.size(),h.size());
		int n=1;
		while(n<n_)n<<=1;
		g.resize(n);h.resize(n);
		vector<Complex> hh=FFT(h);
		vector<Complex> gg=FFT(g);
		vector<Complex> ff(n);
		REP(i,n) ff[i]=gg[i]*hh[i];
		vector<Complex> res=FFT(ff,1);
		REP(i,n) res[i]/=n;
		return res;
	}
}


int main(){
	int n;cin>>n;
	vector<Complex> g(n*2+1),h(n*2+1);
	REP(i,n){int a,b;cin>>a>>b;g[i+1]=a;h[i+1]=b;}
	vector<Complex> f=FFT::convolution(g,h);
	FOR(i,1,n*2+1) cout<<(int)(f[i].real()+0.5) <<endl;
}

Submission Info

Submission Time
Task C - 高速フーリエ変換
User ish_774
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1296 Byte
Status AC
Exec Time 3113 ms
Memory 81020 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 33
Set Name Test Cases
Sample 00_sample_01
All 00_sample_01, 01_00_01, 01_01_19, 01_02_31, 01_03_22, 01_04_31, 01_05_40, 01_06_15, 01_07_39, 01_08_28, 01_09_30, 01_10_23, 01_11_33, 01_12_11, 01_13_28, 01_14_41, 01_15_26, 01_16_49, 01_17_34, 01_18_02, 01_19_33, 01_20_29, 02_00_51254, 02_01_82431, 02_02_17056, 02_03_34866, 02_04_6779, 02_05_65534, 02_06_65535, 02_07_65536, 02_08_65537, 02_09_65538, 02_10_100000
Case Name Status Exec Time Memory
00_sample_01 AC 57 ms 948 KB
01_00_01 AC 26 ms 920 KB
01_01_19 AC 28 ms 932 KB
01_02_31 AC 26 ms 1056 KB
01_03_22 AC 26 ms 1048 KB
01_04_31 AC 28 ms 1052 KB
01_05_40 AC 28 ms 1052 KB
01_06_15 AC 27 ms 860 KB
01_07_39 AC 29 ms 1048 KB
01_08_28 AC 26 ms 1048 KB
01_09_30 AC 27 ms 1052 KB
01_10_23 AC 28 ms 928 KB
01_11_33 AC 28 ms 1052 KB
01_12_11 AC 26 ms 920 KB
01_13_28 AC 27 ms 1048 KB
01_14_41 AC 26 ms 980 KB
01_15_26 AC 31 ms 936 KB
01_16_49 AC 28 ms 1052 KB
01_17_34 AC 28 ms 1056 KB
01_18_02 AC 26 ms 928 KB
01_19_33 AC 27 ms 1056 KB
01_20_29 AC 27 ms 928 KB
02_00_51254 AC 1488 ms 38176 KB
02_01_82431 AC 3027 ms 78944 KB
02_02_17056 AC 688 ms 18116 KB
02_03_34866 AC 1419 ms 36012 KB
02_04_6779 AC 195 ms 6096 KB
02_05_65534 AC 1573 ms 39776 KB
02_06_65535 AC 1612 ms 39836 KB
02_07_65536 AC 2923 ms 76828 KB
02_08_65537 AC 2928 ms 76828 KB
02_09_65538 AC 2937 ms 76820 KB
02_10_100000 AC 3113 ms 81020 KB