結果

問題 No.1618 Convolution?
コンテスト
ユーザー beet
提出日時 2021-07-22 21:43:22
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,110 bytes
コンパイル時間 6,640 ms
コンパイル使用メモリ 249,700 KB
最終ジャッジ日時 2025-01-23 06:24:14
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:138:11: error: reference to 'identity' is ambiguous
  138 |   auto is=identity(n+1);
      |           ^~~~~~~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/iterator_concepts.h:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_iterator_base_types.h:71,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:65,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/specfun.h:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/cmath:1935,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:41,
                 from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/ranges_cmp.h:47:10: note: candidates are: 'struct std::identity'
   47 |   struct identity
      |          ^~~~~~~~
main.cpp:123:13: note:                 'std::vector<long long int> identity(Int)'
  123 | vector<Int> identity(Int n){
      |             ^~~~~~~~

ソースコード

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