Submission #2975594
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
complex<double> W(int n,int i){
return complex<double>(cos(2*M_PI*i/n),sin(2*M_PI*i/n));
}
unsigned int bitrev(int n, unsigned int x){
x = (x & 0x55555555u)<<1 | (x & 0xaaaaaaaau)>>1;
x = (x & 0x33333333u)<<2 | (x & 0xccccccccu)>>2;
x = (x & 0x0f0f0f0fu)<<4 | (x & 0xf0f0f0f0u)>>4;
x = (x & 0x00ff00ffu)<<8 | (x & 0xff00ff00u)>>8;
x = (x & 0x0000ffffu)<<16 | (x & 0xffff0000u)>>16;
return x>>(32-n);
}
void fft(int lgN, complex<double> *f, complex<double> *g){
complex<double>* h[2];
h[0]=new complex<double>[1<<lgN];
h[1]=new complex<double>[1<<lgN];
bool p=true;
for(int i=0;i<(1<<lgN);i++){
h[0][i]=f[i];
}
for(int s=0;s<lgN;s++){
for(int b=0;b<(1<<s);b++){
for(int i=0;i<(1<<(lgN-s));i++){
int j=i+b*(1<<(lgN-s));
if(i<(1<<(lgN-s-1))){
h[p][j]=h[!p][j]+h[!p][j+(1<<(lgN-s-1))];
}else{
h[p][j]=h[!p][j-(1<<(lgN-s-1))]-h[!p][j];
h[p][j]*=W(1<<(lgN-s),j-(1<<(lgN-s-1)));
}
}
}
p=!p;
}
for(int i=0;i<(1<<lgN);i++){
int r=bitrev(lgN,i);
if(i>=r){
g[i]=h[!p][r];
g[r]=h[!p][i];
}
}
delete[] h[0];
delete[] h[1];
}
void fft(int lgN, double *f, complex<double> *g){
complex<double> *h=new complex<double>[1<<lgN];
for(int i=0;i<(1<<lgN);i++){
h[i]=complex<double>(f[i],0);
}
fft(lgN,h,g);
delete[] h;
}
void ifft(int lgN, complex<double> *f, complex<double> *g){
complex<double> *h=new complex<double>[1<<lgN];
for(int i=0;i<(1<<lgN);i++){
h[i]=conj(f[i]);
}
fft(lgN,h,g);
for(int i=0;i<(1<<lgN);i++){
g[i]=conj(g[i])/(double)(1<<lgN);
}
delete[] h;
}
long long round_ll(double x){
if(x>0){
return (long long)(x+0.5);
}else{
return (long long)(x-0.5);
}
}
void hadamard(int N, complex<double> *x, complex<double> *y, complex<double> *ans){
for(int i=0;i<N;i++){
ans[i]=x[i]*y[i];
}
}
int main(){
int N;
double *A,*B;
const int lgMAX=18;
complex<double> *AA,*BB,*CC,*C;
A=new double[1<<lgMAX];
B=new double[1<<lgMAX];
AA=new complex<double>[1<<lgMAX];
BB=new complex<double>[1<<lgMAX];
CC=new complex<double>[1<<lgMAX];
C=new complex<double>[1<<lgMAX];
cin >> N;
int lgN=(int)ceil(log(2*N)/log(2));
for(int i=0;i<N;i++){
cin >> A[i] >> B[i];
}
for(int i=N;i<(1<<lgN);i++){
A[i]=B[i]=0;
}
fft(lgN,A,AA);
fft(lgN,B,BB);
hadamard(1<<lgN,AA,BB,CC);
ifft(lgN,CC,C);
cout << 0 << endl;
for(int i=0;i<2*N-1;i++){
cout << round_ll(C[i].real()) << endl;
}
delete[] A,B,AA,BB,CC,C;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 高速フーリエ変換 |
User |
wisteria0410ss |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3069 Byte |
Status |
AC |
Exec Time |
1384 ms |
Memory |
35072 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 |
7 ms |
16640 KB |
01_00_01 |
AC |
7 ms |
16640 KB |
01_01_19 |
AC |
7 ms |
16640 KB |
01_02_31 |
AC |
7 ms |
16640 KB |
01_03_22 |
AC |
7 ms |
16640 KB |
01_04_31 |
AC |
7 ms |
16640 KB |
01_05_40 |
AC |
7 ms |
16640 KB |
01_06_15 |
AC |
7 ms |
16640 KB |
01_07_39 |
AC |
7 ms |
16640 KB |
01_08_28 |
AC |
7 ms |
16640 KB |
01_09_30 |
AC |
7 ms |
16640 KB |
01_10_23 |
AC |
7 ms |
16640 KB |
01_11_33 |
AC |
7 ms |
16640 KB |
01_12_11 |
AC |
7 ms |
16640 KB |
01_13_28 |
AC |
7 ms |
16640 KB |
01_14_41 |
AC |
7 ms |
16640 KB |
01_15_26 |
AC |
7 ms |
16640 KB |
01_16_49 |
AC |
7 ms |
16640 KB |
01_17_34 |
AC |
7 ms |
16640 KB |
01_18_02 |
AC |
7 ms |
16640 KB |
01_19_33 |
AC |
7 ms |
16640 KB |
01_20_29 |
AC |
7 ms |
16640 KB |
02_00_51254 |
AC |
683 ms |
26996 KB |
02_01_82431 |
AC |
1313 ms |
33024 KB |
02_02_17056 |
AC |
301 ms |
20736 KB |
02_03_34866 |
AC |
620 ms |
24832 KB |
02_04_6779 |
AC |
86 ms |
17664 KB |
02_05_65534 |
AC |
741 ms |
24832 KB |
02_06_65535 |
AC |
746 ms |
24832 KB |
02_07_65536 |
AC |
739 ms |
24832 KB |
02_08_65537 |
AC |
1250 ms |
35072 KB |
02_09_65538 |
AC |
1250 ms |
33024 KB |
02_10_100000 |
AC |
1384 ms |
33024 KB |