結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2020-12-04 01:08:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 5,000 ms |
コード長 | 3,369 bytes |
コンパイル時間 | 1,933 ms |
コンパイル使用メモリ | 181,012 KB |
実行使用メモリ | 14,080 KB |
最終ジャッジ日時 | 2024-09-14 11:03:12 |
合計ジャッジ時間 | 4,344 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;//template#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)#define ALL(v) (v).begin(),(v).end()typedef long long int ll;const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}//endnamespace FFT{struct C{double x,y;C(double _x=0,double _y=0):x(_x),y(_y){}C operator~()const{return C(x,-y);}C operator*(const C& c)const{return C(x*c.x-y*c.y,x*c.y+y*c.x);}C operator+(const C& c)const{return C(x+c.x,y+c.y);}C operator-(const C& c)const{return C(x-c.x,y-c.y);}};vector<vector<C>> w(1,vector<C>(1,1));void init(int lg){for(int d=1,m=1;d<=lg;d++,m<<=1)if(d>=(int)w.size()){w.emplace_back(m);const double th=M_PI/m;for(int i=0;i<m;i++)w[d][i]=(i&1?C(cos(th*i),sin(th*i)):w[d-1][i>>1]);}}void fft(vector<C>& f,bool inv){const int n=f.size(); const int lg=__lg(n);if(lg>=(int)w.size())init(lg);if(inv){for(int k=1;k<=lg;k++){const int d=1<<(k-1);for(int s=0;s<n;s+=2*d){for(int i=s;i<s+d;i++){C x=f[i],y=~w[k][i-s]*f[d+i];f[i]=x+y; f[d+i]=x-y;}}}}else{for(int k=lg;k;k--){const int d=1<<(k-1);for(int s=0;s<n;s+=2*d){for(int i=s;i<s+d;i++){C x=f[i],y=f[d+i];f[i]=x+y; f[d+i]=w[k][i-s]*(x-y);}}}}}vector<ll> mult(const vector<int>& a,const vector<int>& b){const int as=a.size(); const int bs=b.size();if(!as or !bs)return {};const int cs=as+bs-1; vector<ll> c(cs);if(max(as,bs)<16){for(int i=0;i<as;i++)for(int j=0;j<bs;j++){c[i+j]+=(int)a[i]*b[j];}return c;}const int n=1<<__lg(2*cs-1); vector<C> f(n);for(int i=0;i<as;i++)f[i].x=a[i];for(int i=0;i<bs;i++)f[i].y=b[i];fft(f,0); static const C rad(0,-.25);for(int i=0;i<n;i++){int j=i?i^((1<<__lg(i))-1):0;if(i>j)continue;C x=f[i]+~f[j],y=f[i]-~f[j];f[i]=x*y*rad; f[j]=~f[i];}fft(f,1); for(int i=0;i<cs;i++)c[i]=f[i].x/n+.5;return c;}vector<ll> square(const vector<short>& a){const int as=a.size(); if(!as)return {};const int cs=as*2-1; vector<ll> c(cs);if(as<16){for(int i=0;i<as;i++)for(int j=0;j<as;j++){c[i+j]+=(int)a[i]*a[j];}return c;}const int n=1<<__lg(cs*2-1); vector<C> f(n);for(int i=0;i<as;i++)f[i].x=a[i]; fft(f,0);for(int i=0;i<n;i++)f[i]=f[i]*f[i];fft(f,1); for(int i=0;i<cs;i++)c[i]=f[i].x/n+.5;return c;}}int main(){int n,q; cin>>n>>q;vector<int> a(n),cnt(n);rep(i,0,n)cin>>a[i];rep(i,0,q){int x; cin>>x;cnt[x]++;}reverse(ALL(a));auto c=FFT::mult(a,cnt);c.push_back(0);rep(i,0,n){ll res=c[n-1-i]+c[2*n-1-i];cout<<res<<(i==n-1?'\n':' ');}return 0;}