結果
問題 |
No.1307 Rotate and Accumulate
|
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
//#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; }