Submit Info #21146

Problem Lang User Status Time Memory
Convolution (mod 1,000,000,007) cpp (anonymous) WA 961 ms 124.08 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 1 ms 0.67 MiB
fft_killer_00 WA 950 ms 124.01 MiB
fft_killer_01 WA 960 ms 124.01 MiB
max_ans_zero_00 WA 950 ms 124.08 MiB
max_random_00 WA 947 ms 124.03 MiB
max_random_01 WA 961 ms 124.03 MiB
medium_00 WA 9 ms 2.62 MiB
medium_01 WA 8 ms 1.70 MiB
medium_02 WA 11 ms 2.56 MiB
medium_all_zero_00 AC 8 ms 2.45 MiB
random_00 WA 921 ms 120.45 MiB
random_01 WA 900 ms 121.54 MiB
random_02 WA 398 ms 61.10 MiB
small_00 AC 1 ms 0.60 MiB
small_01 AC 1 ms 0.66 MiB
small_02 AC 0 ms 0.62 MiB
small_03 AC 1 ms 0.67 MiB
small_04 AC 2 ms 0.67 MiB
small_05 AC 3 ms 0.67 MiB
small_06 AC 4 ms 0.67 MiB
small_07 AC 1 ms 0.67 MiB
small_08 AC 0 ms 0.62 MiB
small_09 AC 2 ms 0.67 MiB
small_10 AC 1 ms 0.62 MiB
small_11 AC 1 ms 0.67 MiB
small_12 AC 1 ms 0.67 MiB
small_13 AC 4 ms 0.64 MiB
small_14 AC 1 ms 0.68 MiB
small_15 AC 2 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 = long double; using Complex = complex<dbl>; const int MOD = 1000000007; const dbl PI = acosl(-1.0); const int N = 1 << 21; int A[N], B[N]; Complex RA[N], RB[N], w[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) { 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; } for (int i = 0; i < len; ++i) { A[i] = (i < (int)a.size() ? a[i] : 0); B[i] = (i < (int)b.size() ? b[i] : 0); w[i] = polar((dbl)1.0, 2 * PI * i / len); } fft(w, A, RA, len); fft(w, B, RB, len); for (int i = 0; i < len; ++i) { RA[i] *= RB[i]; RA[i] *= Complex(1.0 / len, 0); w[i] = conj(w[i]); } fft(w, RA, RB, len); vector <int> res; for (int i = 0; i < len; ++i) { res.push_back((long long)(RB[i].real() + .5) % 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; }