Submission #579404

#	Time	Username	Problem	Language	Result	Execution time	Memory
579404		KoD	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	501 ms	193824 KiB

xorsum

#include <bits/stdc++.h>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

using ll = long long;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

constexpr int MOD = 1000000007;

struct Fp {
    int x;
    Fp(const int x = 0) : x(x) {}

    Fp operator+(const Fp& t) { return Fp(*this) += t; }
    Fp& operator+=(const Fp& t) {
        x += t.x;
        if (x >= MOD)
            x -= MOD;
        return *this;
    }

    Fp operator-(const Fp& t) { return Fp(*this) -= t; }
    Fp& operator-=(const Fp& t) {
        x -= t.x;
        if (x < 0)
            x += MOD;
        return *this;
    }

    Fp operator*(const Fp& t) { return Fp(*this) *= t; }
    Fp& operator*=(const Fp& t) {
        x = (long long)x * t.x % MOD;
        return *this;
    }

    Fp pow(int e) const {
        Fp ret(1), mul(*this);
        while (e > 0) {
            if (e & 1)
                ret *= mul;
            mul *= mul;
            e >>= 1;
        }
        return ret;
    }
};

constexpr int MAX = 1001;
int A[MAX];
int C1[7][MAX];
int C2[7][7][MAX][MAX];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }
    int Q;
    std::cin >> Q;
    for (int q = 0; q < Q; ++q) {
        int l, r, x;
        std::cin >> l >> r >> x;
        l -= 1;
        for (int d = 0; d < 7; ++d) {
            if (x >> d & 1) {
                C1[d][l] += 1;
                C1[d][r] -= 1;
                for (int e = 0; e < 7; ++e) {
                    if (x >> e & 1) {
                        C2[d][e][l][l] += 1;
                        C2[d][e][l][r] -= 1;
                        C2[d][e][r][l] -= 1;
                        C2[d][e][r][r] += 1;
                    }
                }
            }
        }
    }
    for (int d = 0; d < 7; ++d) {
        for (int i = 1; i <= N; ++i) {
            C1[d][i] += C1[d][i - 1];
        }
    }
    for (int d = 0; d < 7; ++d) {
        for (int e = 0; e < 7; ++e) {
            for (int i = 0; i <= N; ++i) {
                for (int j = 0; j <= N; ++j) {
                    if (i > 0)
                        C2[d][e][i][j] += C2[d][e][i - 1][j];
                    if (j > 0)
                        C2[d][e][i][j] += C2[d][e][i][j - 1];
                    if (i > 0 and j > 0)
                        C2[d][e][i][j] -= C2[d][e][i - 1][j - 1];
                }
            }
        }
    }
    Fp ans = 0;
    array<Fp, 4> inv = {};
    inv[0] = 1;
    for (int k = 0; k < 3; ++k) {
        inv[k + 1] = inv[k] * ((MOD + 1) / 2);
    }
    for (int d = 0; d < 7; ++d) {
        for (int e = 0; e < 7; ++e) {
            for (int i = 0; i < N; ++i) {
                for (int j = i; j < N; ++j) {
                    Fp coeff = Fp(1 << (d + e)) * (i == j ? 1 : 2) * (i + 1) * (N - j);
                    int c1 = C1[d][i], c2 = C1[e][j], c3 = C2[d][e][i][j];
                    c1 -= c3, c2 -= c3;
                    const int b0 = (A[i] >> d) & 1, b1 = (A[j] >> e) & 1;
                    const int t = (c1 > 0) + (c2 > 0) + (c3 > 0);
                    if (t >= 2) {
                        coeff *= inv[2];
                    } else if (c1 > 0) {
                        if (b1 == 0)
                            coeff = 0;
                        else
                            coeff *= inv[1];
                    } else if (c2 > 0) {
                        if (b0 == 0)
                            coeff = 0;
                        else
                            coeff *= inv[1];
                    } else if (c3 > 0) {
                        coeff *= b0 == b1 ? inv[1] : 0;
                    } else {
                        coeff *= b0 and b1;
                    }
                    ans += coeff;
                }
            }
        }
    }
    ans *= Fp(2).pow(Q);
    std::cout << ans.x << '\n';
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 30 / 30
• Subtask 9: 8 / 8