Submission #7577531

---

Source Code Expand

#include <iostream>
#include <cmath>
#include <vector>
#include <complex>

using Real = long double;
using std::vector;
using std::complex;
using Complex = complex<Real>;

const Real PI = std::acos(-1);

vector<Complex> dft(vector<Complex> f, bool isinv) {
    int n = f.size();
    if (n == 1) return f;
    vector<vector<Complex>> ff(2, vector<Complex>(n / 2));
    for (int i = 0; i < n; ++i) {
        ff[i & 1][i >> 1] = f[i];
    }
    for (auto& v : ff) v = dft(v, isinv);

    Complex zeta = std::polar(1.0l, 2 * PI / n);
    if (isinv) zeta = conj(zeta);

    Complex powzeta = 1;
    for (int i = 0; i < n; ++i) {
        f[i] = ff[0][i % (n / 2)] + powzeta * ff[1][i % (n / 2)];
        powzeta *= zeta;
    }
    return f;
}

vector<Complex> mult(vector<Complex> g, vector<Complex> h) {
    int n = 1;
    while (n < g.size() + h.size() + 1) n <<= 1;
    g.resize(n, 0), h.resize(n, 0);

    vector<Complex> gg = dft(g, false), hh = dft(h, false);
    vector<Complex> ff(n);
    for (int i = 0; i < n; ++i) ff[i] = gg[i] * hh[i];

    vector<Complex> f = dft(ff, true);
    for (auto& x : f) x /= n;
    return f;
}

int main() {
    int n;
    std::cin >> n;
    vector<Complex> a(n + 1), b(n + 1);
    a[0] = b[0] = 0;
    for (int i = 1; i <= n; ++i) {
        Real x;
        std::cin >> x;
        a[i] = x;
        std::cin >> x;
        b[i] = x;
    }

    auto ans = mult(a, b);
    for (int i = 1; i <= 2 * n; ++i) {
        std::cout << static_cast<int>(std::round(ans[i].real())) << std::endl;
    }
    return 0;
}

Submission Info

Judge Result