結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2020-12-04 00:19:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 182 ms / 5,000 ms |
コード長 | 1,826 bytes |
コンパイル時間 | 1,412 ms |
コンパイル使用メモリ | 123,980 KB |
最終ジャッジ日時 | 2025-01-16 14:58:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<iostream>#include<string>#include<algorithm>#include<vector>#include<iomanip>#include<math.h>#include<complex>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#include<bitset>#include<functional>#include<assert.h>#include<numeric>using namespace std;#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )#define rep(i,n) REP(i,0,n)using ll = long long;constexpr int inf=1e9+7;constexpr ll longinf=1LL<<60 ;constexpr ll mod=1e9+7 ;typedef vector<complex<double>> poly;const double pi=acos(-1);poly dft(poly f,int rev){int n=f.size();int j=0;REP(i,1,n-1){for(int k=n/2;k>(j^=k);k>>=1);if(i<j)swap(f[i],f[j]);}complex<double> zeta,ret,t,s;for(int i=1;i<n;i<<=1){zeta=polar(1.0,pi/i*rev);for(int j=0;j<n;j+=2*i){ret=1.0;rep(k,i){s=f[j+k];t=f[j+k+i];t=complex<double>(t.real()*ret.real()-t.imag()*ret.imag(),t.imag()*ret.real()+t.real()*ret.imag());f[j+k]=s+t;f[j+k+i]=s-t;ret*=zeta;}}}if(rev==-1)rep(i,n)f[i]/=n;return f;}poly fft(poly g,poly h){poly f;int m=(int)g.size()+h.size()+1;int sz=1;while(sz<m)sz*=2;f.resize(sz,0);g.resize(sz,0);h.resize(sz,0);g=dft(g,1);h=dft(h,1);rep(i,sz)f[i]=g[i]*h[i];f=dft(f,-1);return f;}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n,q;cin>>n>>q;vector<complex<double>> a(n);rep(i,n)cin>>a[i];rep(i,n)a.push_back(a[i]);vector<complex<double>> b(n);rep(i,q){int x;cin>>x;b[n-x-1]+=1;}auto ans = fft(a, b);rep(i,n)cout<<(int)(ans[n-1+i].real()+.5)<<" \n"[i+1==n];return 0;}