Submission #679466

#TimeUsernameProblemLanguageResultExecution timeMemory
679466grandmast3rIntergalactic ship (IZhO19_xorsum)C++17
17 / 100
2085 ms5888 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define vi vector<int> #define pii pair<int, int> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using namespace std; const int MOD = 1e9 + 7; int add(int a, int b){ a += b; if (a >= MOD){ a -= MOD; } return a; } int sub(int a, int b){ a -= b; if (a < 0){ a += MOD; } return a; } int mul(int a, int b){ return (a * 1ll * b) % MOD; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifdef ON_PC freopen("input.txt", "r", stdin); #endif // freopen("output.txt", "w", stdout); int T = 1; // cin >> T; while (T--){ int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++){ cin >> a[i]; } int q; cin >> q; vector<vector<int>> req(q); for (int id = 0; id < q; id++){ req[id].resize(3); for (int i = 0; i < 3; i++){ cin >> req[id][i]; } } random_shuffle(all(req)); int res = 0; // for (int i = 1; i <= n; i++){ // for (int mask = 0; mask < (1 << q); mask++){ // int x = a[i]; // for (int j = 0; j < q; j++){ // if (mask & (1 << j)){ // if (req[j][0] <= i && i <= req[j][1]){ // x ^= req[j][2]; // } // } // } // res = add(res, mul(mul(x, x), mul(i, n - i + 1))); // } // } for (int i = 1; i <= n; i++){ for (int j = i; j <= n; j++){ vector<vector<vector<int>>> dp0((1 << 7), vector<vector<int>>(7, vector<int>(2))); vector<vector<vector<int>>> dp1((1 << 7), vector<vector<int>>(7, vector<int>(2))); for (int k = 0; k < 7; k++){ dp0[a[i]][k][bool(a[j] & (1 << k))]++; } for (int w = 0; w < q; w++){ dp1 = dp0; int x = 0; int y = 0; if (req[w][0] <= i && i <= req[w][1]){ x = req[w][2]; } if (req[w][0] <= j && j <= req[w][1]){ y = req[w][2]; } for (int s = 0; s < (1 << 7); s++){ for (int k = 0; k < 7; k++){ if (y & (1 << k)){ swap(dp0[s][k][0], dp0[s][k][1]); } dp1[s ^ x][k][0] = add(dp1[s ^ x][k][0], dp0[s][k][0]); dp1[s ^ x][k][1] = add(dp1[s ^ x][k][1], dp0[s][k][1]); } } dp1.swap(dp0); } int segcnt = mul(i, n - j + 1); int t = mul(segcnt, 1 + (i != j)); for (int s = 0; s < (1 << 7); s++){ for (int k = 0; k < 7; k++){ res = add(res, mul(mul(s, mul(dp0[s][k][1], (1 << k))), t)); } } // for (int mask = 0; mask < (1 << q); mask++){ // int x = a[i]; // int y = a[j]; // for (int k = 0; k < q; k++){ // if (mask & (1 << k)){ // if (req[k][0] <= i && i <= req[k][1]){ // x ^= req[k][2]; // } // if (req[k][0] <= j && j <= req[k][1]){ // y ^= req[k][2]; // } // } // } // int segcnt = mul(i, n - j + 1); // res = add(res, mul(mul(2, segcnt), mul(x, y))); // } } } cout << res << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...