Submit Info #2653

Problem Lang User Status Time Memory
Convolution cpp14 Hyado WA 522 ms 56.93 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.59 MiB
example_01 AC 6 ms 0.59 MiB
fft_killer_00 WA 521 ms 56.83 MiB
fft_killer_01 WA 520 ms 56.93 MiB
max_random_00 WA 522 ms 56.84 MiB
max_random_01 WA 520 ms 56.82 MiB
random_00 WA 454 ms 54.96 MiB
random_01 WA 472 ms 55.50 MiB
random_02 WA 232 ms 28.15 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; using db = double; using ld = long double; template<typename T> using V = vector<T>; template<typename T> using VV = vector<vector<T>>; #define fs first #define sc second #define pb push_back #define mp make_pair #define mt make_tuple #define eb emplace_back #define all(v) (v).begin(),(v).end() #define siz(v) (ll)(v).size() #define rep(i,a,n) for(ll i=a;i<(ll)(n);++i) #define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i) #define lb lower_bound #define ub upper_bound #define ENDL '\n' typedef pair<int,int> Pi; typedef pair<ll,ll> PL; const ll mod = 998244353; const ll INF = 1000000099; const ll LINF = (ll)(1e18 +99); const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1}; template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;} template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;} template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;} template<typename T,typename Y> inline T mpow(T a, Y n) { T res = 1; for(;n;n>>=1) { if (n & 1) res = res * a; a = a * a; } return res; } const double PI = acos(-1.0); //const long double PI = acos(-1.0L); using cdb=complex<double>;//53 struct RUNFFT{ static void FFT(bool inv,vector<cdb>& a){// int n=(int)a.size(),L=0; while((1<<L)<n)++L;//aはsizeを2冪に拡張済み //1<<L == n static vector<cdb> ep[30]; if(ep[L].empty()){ for(int i=0;i<n;++i){ ep[L].push_back(polar<double>(1,i*2*PI/n));//n-th root long double } } vector<cdb> b(n); for(int i=1;i<=L;++i){ int w=(1<<(L-i));//border for(int y=0;y<n/2;y+=w){ cdb now=ep[L][y]; if(inv)now=conj(now);//conjugate for(int x=0;x<w;++x){ auto l=a[y<<1|x],v=a[y<<1|x|w]; auto r=cdb(now.real()*v.real()-now.imag()*v.imag(),now.real()*v.imag()+now.imag()*v.real()); b[y|x]=l+r; b[y|x|(n>>1)]=l-r; } } swap(a,b); } } template<typename T> vector<T> get_conv_double(const vector<T>& a,const vector<T>& b){ int A=(int)a.size(),B=(int)b.size(),lg=0; while((1<<lg)<A+B-1)++lg; int N=(1<<lg); vector<cdb> d(N); for(int i=0;i<N;++i)d[i]=cdb(i<A?a[i]:0,i<B?b[i]:0); FFT(false,d); for(int i=0;i<(N>>1)+1;++i){ auto j=i?(N-i):0; cdb x=cdb(d[i].real()+d[j].real(),d[i].imag()-d[j].imag()); cdb y=cdb(d[i].imag()+d[j].imag(),-d[i].real()+d[j].real()); d[i]=x*y/T(4); if(i!=j)d[j]=conj(d[i]); } FFT(true,d); V<T> c(A+B-1); for(int i=0;i<A+B-1;++i){ c[i]=d[i].real()/N; } return c; } }; signed main(){ cin.tie(0);ios::sync_with_stdio(false); cout<<fixed<<setprecision(20); int n,m;cin>>n>>m; V<db> a(n),b(m); rep(i,0,n)cin>>a[i]; rep(i,0,m)cin>>b[i]; RUNFFT F; V<db> c=F.get_conv_double(a,b); rep(i,0,siz(c)){ cout<<(ll)round(c[i]) %mod<<ENDL; } } //( ・ __ ・ ) KEEP BEING ORGANIZED //CHECK overflow,vector_size,what to output?