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 |
|
|
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 |