Submission #17731754

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lint = long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
//#define rep(i,n) for(ll i=a;i<(ll)(n);++i)
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)

/*
#define rep(i,...) for(auto i:range(__VA_ARGS__)) 
inline vector<ll> range(ll n){if(n<=0)return vector<ll>();vector<ll>v(n);iota(all(v),0LL);return v;}
inline vector<ll> range(ll a,ll b){if(b<=a)return vector<ll>();vector<ll>v(b-a);iota(all(v),a);return v;}
*/

/**
 * 
 * @brief 多項式乗算
 * 
 *  
 * mul<double>:
 *  verifed with    :https://atcoder.jp/contests/atc001/tasks/fft_c
 *  submittion      :
 * mul<complex<double>>     :
 * mul<modint<1000000007>>  :
 * 
 */

using D=double;
const D PI=acos(D(-1));
using Pc=complex<D>;

void fft(bool type,V<Pc>& a){
    int n=a.size(),s=0;
    while((1<<s)<n)s++;
    assert((1<<s)==n);
    static V<Pc>ep[30];
    if(!ep[s].size()){
        rep(i,0,n){
            ep[s].push_back(polar<D>(1,i*2*PI/n));
        }
    }
    V<Pc>b(n);
    rep(i,1,s+1){
        int w=1<<(s-i);
        for(int y=0;y<n/2;y+=w){
            Pc now=ep[s][y];
            if(type)now=conj(now);
            rep(x,0,w){
                auto l=a[y<<1|x];
                auto u=now,v=a[y<<1|x|w];
                // auto r=Pc(
                //     u.real()*v.real()-u.imag()*v.imag(),
                //     u.real()*v.imag()+u.imag()*v.real()
                // );
                auto r=u*v;
                b[y|x]=l+r;
                b[y|x|n>>1]=l-r;
            }
        }
        swap(a,b);
    }
}

V<D>mul(const V<D>&a,const V<D>&b){
    int s=a.size(),t=b.size(),lg=0;
    if(!s||!t)return {};
    while((1<<lg)<s+t-1)lg++;
    int n=1<<lg;
    V<Pc>c(n);
    rep(i,0,s)c[i].real(a[i]);
    rep(i,0,t)c[i].imag(b[i]);
    fft(false,c);
    rep(i,0,n/2+1){
        const int j=i?n-i:0;
        c[i]=(c[i]+conj(c[j]))*(c[i]-conj(c[j]))*Pc(0,-.25l);
        if(i!=j)c[j]=conj(c[i]);
    }
    fft(true,c);
    V<D>d(s+t-1);
    rep(i,0,s+t-1){
        d[i]=c[i].real()/D(n);
    }
    return d;
}

int main(){
    lint n;
    cin>>n;
    vector<double>a(n+1),b(n+1);
    rep(i,0,n)cin>>a[i+1]>>b[i+1];
    auto c=mul(a,b);
    rep(i,1,2*n+1){
        cout<<(int)round(c[i])<<endl;
    }
}

Submission Info

Judge Result