Submission #556471

#	Time	Username	Problem	Language	Result	Execution time	Memory
556471		cloudholic	씽크스몰 (kriii3_TT)	C++17	30 / 30	2569 ms	222412 KiB

tt

#define _USE_MATH_DEFINES

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

using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define int64 long long

typedef complex<double> base;

void fft(vector <base>& a, const bool invert)
{
    const int n = sz(a);
    for (int i = 1, j = 0; i < n; i++)
    {
        int bit = n >> 1;
        for (; j >= bit; bit >>= 1)
            j -= bit;
        j += bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    vector<base> root(n / 2);
    const double angle = 2 * acos(-1) / n * (invert ? -1 : 1);

    for (int i = 0; i < n / 2; i++)
        root[i] = base(cos(angle * i), sin(angle * i));

    for (int len = 2; len <= n; len <<= 1)
    {
	    const int step = n / len;

        for (int i = 0; i < n; i += len)
        {
            for (int j = 0; j < len / 2; j++)
            {
                base u = a[i + j];
                base v = a[i + j + len / 2] * root[step * j];

                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
            }
        }
    }

    if (invert)
        for (int i = 0; i < n; i++)
            a[i] /= n;
}

void multiply(const vector<int>& a, const vector<int>& b, vector<int64>& res)
{
    constexpr int cut = 1e3;

    vector<base> lower_a, upper_a;
    vector<base> lower_b, upper_b;

    int n = 1;
    while (n < sz(a) + sz(b) - 1)
        n <<= 1;

    lower_a.resize(n);
    upper_a.resize(n);
    lower_b.resize(n);
    upper_b.resize(n);

    for (int i = 0; i < sz(a); i++)
    {
        lower_a[i] = a[i] % cut;
        upper_a[i] = a[i] / cut;
    }
    for (int i = 0; i < sz(b); i++)
    {
        lower_b[i] = b[i] % cut;
        upper_b[i] = b[i] / cut;
    }

    fft(lower_a, false);
	fft(upper_a, false);
    fft(lower_b, false);
	fft(upper_b, false);

    vector<base> lower_a2(all(lower_a));
    vector<base> upper_a2(all(upper_a));

    for (int i = 0; i < n; i++)
    {
        lower_a[i] *= lower_b[i];
        lower_a2[i] *= upper_b[i];
        upper_a[i] *= lower_b[i];
        upper_a2[i] *= upper_b[i];
    }

    fft(lower_a, true);
    fft(lower_a2, true);
    fft(upper_a, true);
    fft(upper_a2, true);

    res.resize(n);

    for (int i = 0; i < n; i++)
    {
	    const int64 res_ll = static_cast<int64>(lower_a[i].real() + (lower_a[i].real() > 0 ? 0.5 : -0.5));
	    const int64 res_lu = static_cast<int64>(lower_a2[i].real() + (lower_a2[i].real() > 0 ? 0.5 : -0.5));
	    const int64 res_ul = static_cast<int64>(upper_a[i].real() + (upper_a[i].real() > 0 ? 0.5 : -0.5));
	    const int64 res_uu = static_cast<int64>(upper_a2[i].real() + (upper_a2[i].real() > 0 ? 0.5 : -0.5));

        res[i] = res_uu * cut * cut + (res_lu + res_ul) * cut + res_ll;
    }
}

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

    int n, m;
    cin >> n >> m;

    vector<int> f, g;
	vector<int64> res;

    f.resize(n + 1);
    g.resize(m + 1);

    for (int i = 0; i <= n; i++)
        cin >> f[i];
    for (int i = 0; i <= m; i++)
        cin >> g[i];

    multiply(f, g, res);

    int64 result = 0;
    for (const auto& i : res)
        result ^= i;

    cout << result << "\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10