結果

問題 No.1307 Rotate and Accumulate
コンテスト
ユーザー Nachia
提出日時 2020-12-04 00:11:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 185 ms / 5,000 ms
コード長 1,268 bytes
コンパイル時間 2,531 ms
コンパイル使用メモリ 199,060 KB
最終ジャッジ日時 2025-01-16 14:56:46
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#include<atcoder/all>
//using namespace atcoder;
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(int i=0;i<(n);i++)

using C = complex<double>;
double pi = acos(-1.0);

void FFT(vector<C>& A, bool inv) {
 int N=A.size();
 for(int i=0,j=0; j<N; j++){
  if(i<j) swap(A[i],A[j]);
  for(int k=N>>1; k>(i^=k); k>>=1);
 }
 for(int i=1; i<N; i<<=1){
  C q = C(cos(pi/i),sin(pi/i)*(inv?1.0:-1.0));
  C qj = C(1.0,0.0);
  rep(j,i){
   for(int k=j; k<N; k+=i*2){
    C l=A[k], r=A[k+i]*qj;
    A[k]=l+r;
    A[k+i]=l-r;
   }
   qj*=q;
  }
 }
 if(inv) rep(i,N) A[i]/=N;
}

vector<C> CONV(const vector<C>& A,const vector<C>& B) {
 int Z=1; while(Z<A.size()+B.size()) Z<<=1;
 vector<C> Ax(Z),Bx(Z);
 rep(i,Z) Ax[i]=Bx[i]=0;
 rep(i,A.size()) Ax[i]=A[i];
 rep(i,B.size()) Bx[i]=B[i];
 FFT(Ax,false);
 FFT(Bx,false);
 rep(i,Z) Ax[i]*=Bx[i];
 FFT(Ax,true);
 return move(Ax);
}

int main(){
  int N,Q; cin>>N>>Q;
  vector<C> A(N); rep(i,N){ int a; cin>>a; A[i]=C((double)a,0.); }
  vector<C> R(N+1); rep(i,Q){ int r; cin>>r; R[N-r]+=C(1.,0.); }
  vector<C> G = CONV(A,R);
  vector<LL> ans(N);
  rep(i,G.size()) ans[i%N] += LL(G[i].real()+0.5);
  rep(i,N){ if(i) cout<<" "; cout<<ans[i]; } cout<<endl;

  return 0;
}
0