結果

問題 No.1618 Convolution?
ユーザー beetbeet
提出日時 2021-07-22 21:43:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 471 ms / 2,000 ms
コード長 3,110 bytes
コンパイル時間 2,658 ms
コンパイル使用メモリ 210,596 KB
実行使用メモリ 51,424 KB
最終ジャッジ日時 2024-07-17 17:02:39
合計ジャッジ時間 11,916 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 424 ms
48,760 KB
testcase_03 AC 418 ms
50,328 KB
testcase_04 AC 216 ms
28,632 KB
testcase_05 AC 24 ms
6,384 KB
testcase_06 AC 430 ms
49,272 KB
testcase_07 AC 431 ms
49,344 KB
testcase_08 AC 215 ms
28,784 KB
testcase_09 AC 454 ms
51,240 KB
testcase_10 AC 419 ms
47,860 KB
testcase_11 AC 432 ms
50,556 KB
testcase_12 AC 465 ms
51,376 KB
testcase_13 AC 435 ms
51,296 KB
testcase_14 AC 471 ms
51,292 KB
testcase_15 AC 434 ms
51,420 KB
testcase_16 AC 453 ms
51,424 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=Int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}


namespace FFT{
  using dbl = long double;

  struct num{
    dbl x,y;
    num(){x=y=0;}
    num(dbl x,dbl y):x(x),y(y){}
  };

  inline num operator+(num a,num b){
    return num(a.x+b.x,a.y+b.y);
  }
  inline num operator-(num a,num b){
    return num(a.x-b.x,a.y-b.y);
  }
  inline num operator*(num a,num b){
    return num(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
  }
  inline num conj(num a){
    return num(a.x,-a.y);
  }

  Int base=1;
  vector<num> rts={{0,0},{1,0}};
  vector<Int> rev={0,1};

  const dbl PI=asinl(1)*2;

  void ensure_base(Int nbase){
    if(nbase<=base) return;

    rev.resize(1<<nbase);
    for(Int i=0;i<(1<<nbase);i++)
      rev[i]=(rev[i>>1]>>1)+((i&1)<<(nbase-1));

    rts.resize(1<<nbase);
    while(base<nbase){
      dbl angle=2*PI/(1<<(base+1));
      for(Int i=1<<(base-1);i<(1<<base);i++){
        rts[i<<1]=rts[i];
        dbl angle_i=angle*(2*i+1-(1<<base));
        rts[(i<<1)+1]=num(cos(angle_i),sin(angle_i));
      }
      base++;
    }
  }

  void fft(vector<num> &as){
    Int n=as.size();
    assert((n&(n-1))==0);

    Int zeros=__builtin_ctz(n);
    ensure_base(zeros);
    Int shift=base-zeros;
    for(Int i=0;i<n;i++)
      if(i<(rev[i]>>shift))
        swap(as[i],as[rev[i]>>shift]);

    for(Int k=1;k<n;k<<=1){
      for(Int i=0;i<n;i+=2*k){
        for(Int j=0;j<k;j++){
          num z=as[i+j+k]*rts[j+k];
          as[i+j+k]=as[i+j]-z;
          as[i+j]=as[i+j]+z;
        }
      }
    }
  }

  template<typename T>
  vector<long long> multiply(vector<T> &as,vector<T> &bs){
    Int need=as.size()+bs.size()-1;
    Int nbase=0;
    while((1<<nbase)<need) nbase++;
    ensure_base(nbase);

    Int sz=1<<nbase;
    vector<num> fa(sz);
    for(Int i=0;i<sz;i++){
      T x=(i<(Int)as.size()?as[i]:0);
      T y=(i<(Int)bs.size()?bs[i]:0);
      fa[i]=num(x,y);
    }
    fft(fa);

    num r(0,-0.25/sz);
    for(Int i=0;i<=(sz>>1);i++){
      Int j=(sz-i)&(sz-1);
      num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r;
      if(i!=j)
        fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r;
      fa[i]=z;
    }
    fft(fa);

    vector<long long> res(need);
    for(Int i=0;i<need;i++)
      res[i]=round(fa[i].x);

    return res;
  }

};


vector<Int> identity(Int n){
  vector<Int> ord(n);
  iota(ord.begin(),ord.end(),0);
  return ord;
}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int n;
  cin>>n;
  auto as=read(n);
  auto bs=read(n);
  auto is=identity(n+1);
  as.emplace(as.begin(),0);
  bs.emplace(bs.begin(),0);

  auto xs=FFT::multiply(is,as);
  auto ys=FFT::multiply(is,bs);

  for(Int i=1;i<=n+n;i++){
    if(i!=1) cout<<' ';
    cout<<xs[i]+ys[i];
  }
  cout<<newl;
  return 0;
}
0