Submit Info #21141

Problem Lang User Status Time Memory
Convolution cpp (anonymous) AC 457 ms 38.76 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 2 ms 0.67 MiB
fft_killer_00 AC 455 ms 38.76 MiB
fft_killer_01 AC 445 ms 38.76 MiB
max_ans_zero_00 AC 455 ms 38.76 MiB
max_random_00 AC 457 ms 38.76 MiB
max_random_01 AC 444 ms 38.76 MiB
medium_00 AC 5 ms 1.30 MiB
medium_01 AC 3 ms 1.00 MiB
medium_02 AC 6 ms 1.30 MiB
medium_all_zero_00 AC 4 ms 1.25 MiB
random_00 AC 416 ms 35.53 MiB
random_01 AC 427 ms 36.42 MiB
random_02 AC 170 ms 18.61 MiB
small_00 AC 1 ms 0.67 MiB
small_01 AC 0 ms 0.62 MiB
small_02 AC 2 ms 0.62 MiB
small_03 AC 1 ms 0.62 MiB
small_04 AC 1 ms 0.69 MiB
small_05 AC 1 ms 0.67 MiB
small_06 AC 2 ms 0.67 MiB
small_07 AC 1 ms 0.66 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 2 ms 0.48 MiB
small_10 AC 1 ms 0.62 MiB
small_11 AC 0 ms 0.70 MiB
small_12 AC 1 ms 0.62 MiB
small_13 AC 1 ms 0.67 MiB
small_14 AC 1 ms 0.62 MiB
small_15 AC 1 ms 0.67 MiB

#pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4") #include <bits/stdc++.h> using namespace std; namespace NTT { const int MOD = 998244353; const int N = 1 << 21; int G; int mPow(int a, int n, int mod) { int r = 1; while (n > 0) { if (n & 1) { r = 1LL * r * a % mod; } a = 1LL * a * a % mod; n >>= 1; } return r; } int findGen(int md) { int _phi = md - 1; //phi(md) int val = _phi; vector <int> divisorsPhi; for (int d = 2; d * d <= val; ++d) { if (val % d == 0) { divisorsPhi.push_back(d); } while (val % d == 0) { val /= d; } } if (val > 1) { divisorsPhi.push_back(val); } int g = 2; while (g < md) { bool ok = true; for (auto it : divisorsPhi) { if (mPow(g, _phi / it, md) == 1) { ok = false; break; } } if (ok) { break; } ++g; } assert (g < md); return g >= md ? -1 : g; } void init() { G = findGen(MOD); } int A[N], B[N], RA[N], RB[N], w[N]; void fft(int *w, int *p, int *y, int n, int k = 1) { if (n > 1) { fft(w, p, y, n >>= 1, k << 1); fft(w, p + k, y + n, n, k << 1); for (int i = 0, j = 0; i < n; ++i, j += k) { int r = 1LL * w[j] * y[i + n] % MOD; y[i + n] = (y[i] - r + MOD) % MOD; y[i] = (y[i] + r) % MOD; /* if ((y[i + n] = y[i] - r) < 0) { y[i + n] += MOD; } if ((y[i] += r) >= MOD) { y[i] -= MOD; }*/ } } else { *y = *p; } } int inv(int x) { return x == 1 ? 1 : 1LL * (MOD - MOD / x) * inv(MOD % x) % MOD; } vector <int> mul(vector <int> a, vector <int> b) { if (a.empty() || b.empty()) { return {}; } int len = 1, lg = 0, need = (int)a.size() + (int)b.size() - 1; while (len < need) { len <<= 1; ++lg; } assert ((MOD - 1) % len == 0); int Step = mPow(G, (MOD - 1) / len, MOD); for (int i = 0; i < len; ++i) { A[i] = (i < a.size() ? a[i] : 0); B[i] = (i < b.size() ? b[i] : 0); } for (int i = 0, mul = 1; i < len; ++i) { w[i] = mul; mul = 1LL * mul * Step % MOD; } fft(w, A, RA, len); fft(w, B, RB, len); int div2 = mPow(inv(2), lg, MOD); for (int i = 0, mul = 1; i < len; ++i) { RA[i] = 1LL * RA[i] * RB[i] % MOD; } reverse(w + 1, w + len); fft(w, RA, RB, len); for (int i = 0; i < len; ++i) { RB[i] = 1LL * RB[i] * div2 % MOD; } vector <int> res; for (int i = 0; i < len; ++i) { res.push_back(RB[i]); } res.resize(need); /* while (res.size() > 1 && res.back() == 0) { res.pop_back(); }*/ return res; } }; int main() { // freopen("input.txt", "r", stdin); int n, m; scanf("%d%d", &n, &m); vector <int> a(n); vector <int> b(m); for (auto &it : a) { scanf("%d", &it); } for (auto &jt : b) { scanf("%d", &jt); } reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); NTT::init(); vector <int> c = NTT::mul(a, b); reverse(c.begin(), c.end()); bool first = true; for (auto it : c) { if (!first) { printf(" "); } printf("%d", it); first = false; } printf("\n"); return 0; }