Submit Info #21189

Problem Lang User Status Time Memory
Convolution cpp tonegawa WA 390 ms 64.82 MiB

ケース詳細
Name Status Time Memory
example_00 WA 1 ms 0.67 MiB
example_01 AC 1 ms 0.64 MiB
fft_killer_00 WA 390 ms 64.82 MiB
fft_killer_01 WA 388 ms 64.81 MiB
max_ans_zero_00 WA 386 ms 64.81 MiB
max_random_00 WA 387 ms 64.73 MiB
max_random_01 WA 386 ms 64.74 MiB
medium_00 WA 10 ms 2.61 MiB
medium_01 WA 2 ms 1.61 MiB
medium_02 WA 5 ms 1.64 MiB
medium_all_zero_00 AC 11 ms 2.67 MiB
random_00 WA 370 ms 64.75 MiB
random_01 WA 374 ms 64.80 MiB
random_02 WA 342 ms 64.75 MiB
small_00 AC 1 ms 0.57 MiB
small_01 AC 1 ms 0.57 MiB
small_02 AC 1 ms 0.64 MiB
small_03 AC 1 ms 0.60 MiB
small_04 AC 1 ms 0.67 MiB
small_05 WA 1 ms 0.67 MiB
small_06 WA 1 ms 0.67 MiB
small_07 WA 1 ms 0.67 MiB
small_08 AC 0 ms 0.61 MiB
small_09 WA 2 ms 0.67 MiB
small_10 WA 1 ms 0.62 MiB
small_11 WA 1 ms 0.67 MiB
small_12 AC 1 ms 0.65 MiB
small_13 WA 0 ms 0.61 MiB
small_14 WA 3 ms 0.56 MiB
small_15 WA 3 ms 0.62 MiB

#include <iostream> #include <string> #include <vector> #include <array> #include <queue> #include <deque> #include <algorithm> #include <set> #include <map> #include <bitset> #include <cmath> #include <functional> #include <cassert> #include <iomanip> #define vll vector<ll> #define vvvl vector<vvl> #define vvl vector<vector<ll>> #define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c)) #define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c<b;c++) #define all(obj) (obj).begin(), (obj).end() typedef long long int ll; typedef long double ld; using namespace std; inline ll mpow(ll a, ll b, ll p = -1){ ll ret = 1, num = a; while(b>0){ if(b&1) ret = (ret*num)%p; num = (num*num)%p; b /= 2; } return ret; } template<ll P, ll proot> struct NTT{ ll g; vector<ll> primes; NTT(){}; inline ll mpow(ll a, ll b){ ll ret = 1, num = a; while(b){ if(b&1) ret = (ret*num)%P; num = (num*num)%P, b >>= 1; } return ret; } ll get_mod(){return P;} void ntt(vector<ll>&f, bool inv){ int n, N = f.size(); g = mpow(proot, P/N); vector<ll> angles(N, 1); for(int i=1;i<N;i++) angles[i] = (angles[i-1] * g)%P; for(n=0;;n++) if(N == (1<<n)) break; for (int m=0;m<N;m++) { int m2 = 0; for(int i=0;i<n;i++) if(m&(1<<i)) m2 |= (1<<(n-1-i)); if(m < m2) swap(f[m], f[m2]); } for(int i=0;i<N;i++) f[i] %= P; for(int t=1;t<N;t*=2) { ll w = angles[N/(2*t)]; if(inv) w = angles[N - N/(2*t)]; for(int i=0;i<N;i+=2*t){ ll power = 1; for (int j=0;j<t;j++) { ll tmp1 = (f[i+j] + f[i+t+j] * power)%P; ll tmp2 = f[i+j] - (f[i+t+j] * power)%P; if(tmp2<0) tmp2 += P; f[i+j] = tmp1; f[i+t+j] = tmp2; //power = (power * w)%P; } } } if(inv) { ll inv = mpow(N, P-2); for(int i=0;i<N;i++) f[i] = (f[i]*inv)%P; } } vector<ll> conv(vector<ll> A, vector<ll> B){ assert(A.size()==B.size()); ll N = A.size(); vector<ll> C(N); ntt(A, 0); ntt(B, 0); for(int i=0;i<N;i++) C[i] = (A[i] * B[i])%P; ntt(C, 1); return C; } }; vector<ll> int32mod_conv(vector<ll> a, vector<ll> b, ll P){ for(ll& i:a) i%=P; for(ll& i:b) i%=P; if(P==998244353) return NTT<998244353, 3>().conv(a, b); NTT<167772161, 3> ntt1; NTT<469762049, 3> ntt2; NTT<1224736769, 3> ntt3; vector<ll> A = ntt1.conv(a, b); vector<ll> B = ntt2.conv(a, b); vector<ll> C = ntt3.conv(a, b); ll N = A.size(); vector<ll> ret(N); ll x = ntt1.get_mod(); ll y = ntt2.get_mod(); ll z = ntt3.get_mod(); ll ix = mpow(x, y-2, y); ll ixy = mpow((x*y)%z, z-2, z); for(int i=0;i<N;i++){ ll v = ((B[i] - A[i])*ix)%y; if(v<0) v += y; ll xxv = A[i]+x*v; v = ((C[i] - (xxv%z))*ixy)%z; if(v<0) v += z; ret[i] = ((xxv%P) + ((x*y)%P)*v)%P; } return ret; } inline ll read(){ ll x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } int main(){ ll n, m;scanf("%lld %lld", &n, &m); ll N = 1; while(N<max(n, m)*2) N*=2; vector<ll> A(N, 0), B(N, 0); for(int i=0;i<n;i++) A[i] = read(); for(int i=0;i<m;i++) B[i] = read(); A = int32mod_conv(A, B, 998244353); for(int i=0;i<n+m-1;i++){ if(i==n+m-2) printf("%lld\n", A[i]); else printf("%lld ", A[i]); } }