Submission #531786

#	Time	Username	Problem	Language	Result	Execution time	Memory
531786		abc864197532	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	1397 ms	194040 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    if (a.empty()) return o << "{}";
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv() {}
};
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout); 
#else
#define test(args...) void(0)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 1e9 + 7, N = 1001, logN = 20, K = 111, C = 7;

void trans (vector <lli> &dp, int x) {
    vector <lli> pre = dp;
    for (int i = 0; i < C; ++i) {
        dp[i ^ x] += pre[i];
        if (dp[i ^ x] >= mod)
            dp[i ^ x] -= mod;
    }
}

int pre[N][N][C][C], pw[N << 7];

int main () {
    owo;
    pw[0] = 1;
    for (int i = 1; i < N << 7; ++i) {
        pw[i] = pw[i - 1] + pw[i - 1];
        if (pw[i] >= mod)
            pw[i] -= mod;
    }
    int n, q;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cin >> q;
    for (int i = 0, l, r, x; i < q; ++i) {
        cin >> l >> r >> x, --l;
        // pre[l ~ r][l ~ r]++
        for (int ii = 0; ii < C; ++ii) if (x >> ii & 1)
            for (int jj = 0; jj < C; ++jj) if (x >> jj & 1)
                pre[l][l][ii][jj]++, pre[l][r][ii][jj]--, pre[r][l][ii][jj]--, pre[r][r][ii][jj]++;
    }
    for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int ii = 0; ii < C; ++ii) for (int jj = 0; jj < C; ++jj) {
        if (i && j)
            pre[i][j][ii][jj] -= pre[i - 1][j - 1][ii][jj];
        if (i)
            pre[i][j][ii][jj] += pre[i - 1][j][ii][jj];
        if (j)
            pre[i][j][ii][jj] += pre[i][j - 1][ii][jj];
    }
    lli ans = 0;
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
        for (int ii = 0; ii < C; ++ii) for (int jj = 0; jj < C; ++jj) {
            int cnt11 = pre[i][j][ii][jj], cnt10 = pre[i][i][ii][ii] - cnt11, cnt01 = pre[j][j][jj][jj] - cnt11, cnt00 = q - cnt01 - cnt10 - cnt11;
            int curi[2], curj[2];
            if (cnt10)
                curi[0] = curi[1] = pw[cnt10 - 1];
            else
                curi[0] = 1, curi[1] = 0;
            if (cnt01)
                curj[0] = curj[1] = pw[cnt01 - 1];
            else
                curj[0] = 1, curj[1] = 0;
            int bi = a[i] >> ii & 1, bj = a[j] >> jj & 1, now = 0;
            if (cnt11) {
                now = (1ll * curi[bi] * curj[bj] + 1ll * curi[bi ^ 1] * curj[bj ^ 1]) % mod * pw[cnt11 - 1] % mod;
            } else {
                now = 1ll * curi[bi ^ 1] * curj[bj ^ 1] % mod;
            }
            (ans += 1ll * now % mod * pw[ii + jj] % mod * (min(i, j) + 1) % mod * (n - max(i, j)) % mod * pw[cnt00]) %= mod;
        }
    }
    cout << ans << '\n';
}

• 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