結果

問題 No.1307 Rotate and Accumulate
ユーザー 👑 NachiaNachia
提出日時 2020-12-04 00:11:14
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 162 ms / 5,000 ms
コード長 1,268 bytes
コンパイル時間 2,049 ms
コンパイル使用メモリ 205,448 KB
実行使用メモリ 14,460 KB
最終ジャッジ日時 2023-10-12 10:45:45
合計ジャッジ時間 5,249 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 113 ms
13,548 KB
testcase_09 AC 117 ms
13,616 KB
testcase_10 AC 94 ms
8,544 KB
testcase_11 AC 64 ms
9,128 KB
testcase_12 AC 90 ms
8,604 KB
testcase_13 AC 25 ms
4,348 KB
testcase_14 AC 44 ms
5,596 KB
testcase_15 AC 161 ms
14,400 KB
testcase_16 AC 160 ms
14,232 KB
testcase_17 AC 160 ms
14,460 KB
testcase_18 AC 137 ms
14,160 KB
testcase_19 AC 162 ms
14,220 KB
testcase_20 AC 161 ms
14,236 KB
testcase_21 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

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