Submission #4627519


Source Code Expand

#pragma GCC optimize("-O0")
#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 3117 Byte
Status AC
Exec Time 1728 ms
Memory 33140 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 17 ms 17152 KB
01_00_01 AC 11 ms 16640 KB
01_01_19 AC 11 ms 16640 KB
01_02_31 AC 11 ms 16640 KB
01_03_22 AC 11 ms 16640 KB
01_04_31 AC 11 ms 16640 KB
01_05_40 AC 12 ms 16640 KB
01_06_15 AC 11 ms 16640 KB
01_07_39 AC 12 ms 16640 KB
01_08_28 AC 11 ms 16640 KB
01_09_30 AC 12 ms 18688 KB
01_10_23 AC 11 ms 16640 KB
01_11_33 AC 11 ms 16640 KB
01_12_11 AC 11 ms 16640 KB
01_13_28 AC 11 ms 16640 KB
01_14_41 AC 12 ms 16640 KB
01_15_26 AC 11 ms 16640 KB
01_16_49 AC 12 ms 16640 KB
01_17_34 AC 11 ms 16640 KB
01_18_02 AC 11 ms 16640 KB
01_19_33 AC 11 ms 16640 KB
01_20_29 AC 11 ms 16640 KB
02_00_51254 AC 853 ms 24832 KB
02_01_82431 AC 1663 ms 33024 KB
02_02_17056 AC 387 ms 20736 KB
02_03_34866 AC 794 ms 24832 KB
02_04_6779 AC 108 ms 17664 KB
02_05_65534 AC 907 ms 24832 KB
02_06_65535 AC 914 ms 24832 KB
02_07_65536 AC 907 ms 24832 KB
02_08_65537 AC 1614 ms 33140 KB
02_09_65538 AC 1607 ms 33024 KB
02_10_100000 AC 1728 ms 33024 KB