BOJ 11385 WIP

main.cc

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

using cpx = complex<d64>;

vector<cpx> nrU;  // nth root of unity

void FFT(vector<cpx> &v, i64 idx) {
    const i64 N = v.size();
    if (N == 1) return;

    vector<cpx> odd, even;
    for (int i = 0; i < N; i++) {
        if (i % 2)
            odd.push_back(v[i]);
        else
            even.push_back(v[i]);
    }

    FFT(even, (idx * 2) % nrU.size());
    FFT(odd, (idx * 2) % nrU.size());

    i64 pos = 0;
    for (int i = 0; i < N / 2; i++) {
        cpx tmp = nrU[pos] * odd[i];
        v[i] = even[i] + tmp;
        v[i + N / 2] = even[i] - tmp;
        pos += idx;
        pos %= nrU.size();
    }
}

vector<cpx> convolution(vector<cpx> &a, vector<cpx> &b) {
    i64 N = 1;
    while (N <= a.size() || N <= b.size()) N *= 2;
    N *= 2;

    const d64 PI = acos(-1.L);
    for (i64 i = 0; i < N; i++) {
        d64 theta = 2 * PI * i / N;
        nrU.emplace_back(cpx(cos(theta), sin(theta)));
    }

    a.resize(N), b.resize(N);
    FFT(a, 1), FFT(b, 1);

    vector<cpx> c(N);
    for (int i = 0; i < N; i++) c[i] = a[i] * b[i];

    FFT(c, N - 1);
    for (auto &el : c) el /= cpx(static_cast<d64>(N));

    return c;
}

using ui64 = unsigned long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;
    N++, M++;

    vector<cpx> a(N), b(M);
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < M; i++) cin >> b[i];

    auto c = convolution(a, b);

    vector<ui64> ret;
    transform(iterall(c), back_inserter(ret), [](cpx x) -> ui64 {
        return static_cast<ui64>(x.real() + (x.real() > 0
                                                 ? static_cast<d64>(0.5)
                                                 : static_cast<d64>(-0.5)));
    });
/*
    for (int i = 0; i < ret.size(); i++) {
        if (ret[i] % 100000 != 0) {
            cout << i << " " << ret[i] << endl;
        }
    }
*/
    ui64 ans = 0;
    for (ui64 el : ret) ans ^= el;

    cout << ans << endl;

    return 0;
}