Submission #342326

#	Time	Username	Problem	Language	Result	Execution time	Memory
342326		kekw	Intergalactic ship (IZhO19_xorsum)	C++17	17 / 100	2092 ms	2284 KiB

xorsum

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define range(i, n) for (int i = 0; i < (n); ++i)
#define ar array
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()


typedef long long ll;
typedef long double ld;
using namespace std;

//using namespace __gnu_pbds;

const ll INF = 1e18 + 5;
const int INFi = 1e9;
const int maxN = 1e7 + 1500;
const int md2 = 998244353;
const int md = 1e9 + 7;


int add(int a, int b) {
    if (a + b >= md) return a + b - md;
    return a + b;
}

int sub(int a, int b) {
    if (a - b < 0) return a - b + md;
    return a - b;
}

int mul(int a, int b) {
    return (1ll * a * b) % md;
}

int binpow(int a, int b) {
    if (b <= 0) return 1;
    if (b % 2) return mul(a, binpow(a, b - 1));
    int m = binpow(a, b / 2);
    return mul(m, m);
}


int rev(int a) {
    return binpow(a, md - 2);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    range(i, n) cin >> a[i];
    int q;
    cin >> q;
    vector<ar<int, 3>> b(q);
    range(i, q) range(j, 3) cin >> b[i][j];
    int ans = 0;
    range(i, n) {
        range(b1, 8) {
            range(j, n) {
                range(b2, 8) {
                    vector<int> dp(4);
                    int start = 0;
                    if (a[i] & (1 << b1)) start ^= 1;
                    if (a[j] & (1 << b2)) start ^= 2;
                    dp[start] = 1;
                    range(w, q) {
                        auto dp2 = dp;
                        range(e, 4) {
                            int e2 = e;
                            if (b[w][0] - 1 <= i && i < b[w][1] && (b[w][2] & (1 << b1))) e2 ^= 1;
                            if (b[w][0] - 1 <= j && j < b[w][1] && (b[w][2] & (1 << b2))) e2 ^= 2;
                            dp2[e2] = add(dp2[e2], dp[e]);
                        }
                        swap(dp, dp2);
                    }
                    int l = min(i, j);
                    int r = max(i, j);
                    ans = add(ans, mul(mul(l + 1, n - r), mul(dp[3], mul(1 << b1, 1 << b2))));
                }
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(15) << fixed;
    int tests = 1;
    //cin >> tests;
    range(_, tests) {
        solve();
    }
    return 0;
}

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