Submit Info #21158

Problem Lang User Status Time Memory
Convolution (mod 1,000,000,007) cpp (anonymous) AC 1007 ms 90.79 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 1 ms 0.67 MiB
fft_killer_00 AC 994 ms 90.79 MiB
fft_killer_01 AC 981 ms 90.79 MiB
max_ans_zero_00 AC 981 ms 90.78 MiB
max_random_00 AC 1007 ms 90.79 MiB
max_random_01 AC 969 ms 90.79 MiB
medium_00 AC 7 ms 1.99 MiB
medium_01 AC 7 ms 1.42 MiB
medium_02 AC 4 ms 1.99 MiB
medium_all_zero_00 AC 9 ms 1.80 MiB
random_00 AC 986 ms 85.58 MiB
random_01 AC 932 ms 87.20 MiB
random_02 AC 379 ms 43.88 MiB
small_00 AC 1 ms 0.67 MiB
small_01 AC 2 ms 0.67 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 0 ms 0.68 MiB
small_04 AC 1 ms 0.62 MiB
small_05 AC 2 ms 0.67 MiB
small_06 AC 3 ms 0.65 MiB
small_07 AC 1 ms 0.66 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 1 ms 0.65 MiB
small_10 AC 1 ms 0.64 MiB
small_11 AC 1 ms 0.67 MiB
small_12 AC 3 ms 0.65 MiB
small_13 AC 1 ms 0.67 MiB
small_14 AC 3 ms 0.67 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 FFT { using dbl = double; using Complex = complex<dbl>; const int MOD = 1000000007; const dbl PI = acosl(-1.0); const int N = 1 << 21; const int T = 2, BASE = 32000; int A[T][N], B[T][N], Pow[T << 1]; Complex RA[N], RB[N], w[2][N]; template <class P, class Q> void fft(Complex *w, P *p, Q *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) { Complex r = w[j] * y[i + n]; y[i + n] = y[i] - r; y[i] += r; } } else { *y = *p; } } vector <int> mul(vector <int> a, vector <int> b) { //Ai = sum (i = 0..1) Ci * BASE^i, let's use BASE = MOD^(1/2) 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; } Pow[0] = 1; for (int i = 1; i < T << 1; ++i) { Pow[i] = 1LL * BASE * Pow[i - 1] % MOD; } for (int i = 0; i < len; ++i) { if (i < (int)a.size()) { int ta = a[i]; for (int k = 0; k < T && ta > 0; ++k) { A[k][i] = ta % BASE; ta /= BASE; } } if (i < (int)b.size()) { int tb = b[i]; for (int k = 0; k < T && tb > 0; ++k) { B[k][i] = tb % BASE; tb /= BASE; } } w[0][i] = polar((dbl)1.0, 2 * PI * i / len); w[1][i] = conj(w[0][i]); } vector <int> res(len); for (int it = 0; it < 2; ++it) { for (int jt = 0; jt < 2; ++jt) { for (int i = 0; i < len; ++i) { RA[i] = Complex(A[it][i], B[jt][i]); } fft(w[0], RA, RB, len); for (int i = 0; i < len; ++i) { int u = i, v = (len - i) % len; RA[i] = Complex((RB[u].real() + RB[v].real()) * 0.5, (RB[u].imag() - RB[v].imag()) * 0.5) * Complex((RB[u].imag() + RB[v].imag()) * 0.5, (RB[v].real() - RB[u].real()) * 0.5); } fft(w[1], RA, RB, len); for (int i = 0; i < need; ++i) { res[i] = (res[i] + (long long)(RB[i].real() / len + .5) % MOD * Pow[it + jt]) % MOD; } } } 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()); vector <int> c = FFT::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; }