Submission #2975526

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef unsigned long long ulint;
#define MOD 1000000007
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 abs(int N, complex<double> *x, double *y){
    for(int i=0;i<N;i++){
        y[i]=abs(x[i]);
    }
}
void abs(int N, complex<double> *x, long long *y){
    for(int i=0;i<N;i++){
        y[i]=round_ll(abs(x[i]));
    }
}

void real(int N, complex<double> *x, double *y){
    for(int i=0;i<N;i++){
        y[i]=x[i].real();
    }
}
void real(int N, complex<double> *x, long long *y){
    for(int i=0;i<N;i++){
        y[i]=round_ll(x[i].real());
    }
}

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;
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }
    for(int i=N;i<(1<<lgMAX);i++){
        A[i]=B[i]=0;
    }
    fft(lgMAX,A,AA);
    fft(lgMAX,B,BB);
    hadamard(1<<lgMAX,AA,BB,CC);
    ifft(lgMAX,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

Judge Result