結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2020-12-04 00:43:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 389 ms / 5,000 ms |
コード長 | 1,893 bytes |
コンパイル時間 | 1,996 ms |
コンパイル使用メモリ | 175,684 KB |
実行使用メモリ | 39,512 KB |
最終ジャッジ日時 | 2024-09-14 10:24:12 |
合計ジャッジ時間 | 7,520 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h>using namespace std;//#define int long long#define REP(i,m,n) for(int i=(m);i<(n);i++)#define rep(i,n) REP(i,0,n)#define pb push_back#define all(a) a.begin(),a.end()#define rall(c) (c).rbegin(),(c).rend()#define mp make_pair#define endl '\n'#define vec vector<ll>#define mat vector<vector<ll> >#define fi first#define se secondtypedef long long ll;typedef unsigned long long ull;typedef pair<ll,ll> pll;typedef long double ld;typedef complex<double> Complex;const ll INF=1e9+7;const ll inf=INF*INF;const int mod=1e9+7;const ll MAX=1000010;const double PI=acos(-1.0);//再帰FFTvector<Complex>dft(vector<Complex>A,int N,int sgn=1){if(N==1)return A;vector<Complex>F(N/2),G(N/2);for(int i=0;i<N/2;i++){F[i]=A[2*i+0];G[i]=A[2*i+1];}F=dft(F,N/2,sgn);G=dft(G,N/2,sgn);Complex zeta(cos(2.0*M_PI/N),sin(2.0*M_PI/N)*sgn);Complex pow_zeta=1;for(int i=0;i<N;i++){A[i]=F[i%(N/2)]+pow_zeta*G[i%(N/2)];pow_zeta*=zeta;}return A;}vector<Complex>inv_dft(vector<Complex>A,int N){A=dft(A,N,-1);for(int i=0;i<N;i++){A[i]/=N;}return A;}vector<Complex>multiply(vector<Complex>A,vector<Complex>B){int sz=A.size()+B.size()+1;int N=1;while(N<sz)N*=2;A.resize(N),B.resize(N);A=dft(A,N);B=dft(B,N);vector<Complex>F(N);for(int i=0;i<N;i++){F[i]=A[i]*B[i];}return inv_dft(F,N);}signed main(){ll n,q;cin>>n>>q;vector<Complex>a(n);rep(i,n)cin>>a[i];vector<Complex>c(n);rep(i,q){int r;cin>>r;c[n-1-r]+=1.0;}vector<Complex>b=multiply(c,a);vector<ll>ans(n);rep(i,n){ans[i]=ll(b[i+n-1].real()+0.5);if(i)ans[i]+=ll(b[i-1].real()+0.5);}rep(i,n){cout<<ans[i]<<' ';}cout<<endl;}