Submission #1991671

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

typedef complex<double> Comp;
const double PI=acos(-1.0);
const Comp I(0,1);
void fft(int n,vector<Comp> &a,bool inv=false){
    double zeta=(inv?-1:1)*2*PI/n;
    for(int m=n;m>=2;m>>=1){
        int mh=m>>1;
        rep(i,mh){
            Comp w=exp((double)i*zeta*I);
            for(int j=i;j<n;j+=m){
                int k=j+mh;
                Comp x=a[j]-a[k];
                a[j]+=a[k];
                a[k]=w*x;
            }
        }
        zeta*=2;
    }
    int i=0;
    FOR(j,1,n-1){
        for(int k=n>>1;k>(i^=k);k>>=1);
        if(j<i) swap(a[i],a[j]);
    }
    if(inv) rep(i,n) a[i]/=n;
}
void conv(vector<Comp> &v,vector<Comp> &w){
    int n=1,deg=v.size()+w.size()-1;
    while(n<deg) n<<=1;
    v.resize(n),w.resize(n);
    fft(n,v);fft(n,w);
    rep(i,n) v[i]*=w[i];
    fft(n,v,true);
}

int main(){
    int n;
    cin>>n;
    vector<Comp> a(n+1,0),b(n+1,0);
    FOR(i,1,n+1){
        cin>>a[i]>>b[i];
    }
    conv(a,b);
    FOR(i,1,2*n+1) cout<<(int)(a[i].real()+0.5)<<endl;
    return 0;
}

Submission Info

Judge Result