// https://oj.uz/problem/view/IZhO19_xorsum
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
const int MOD = 1e9 + 7;
int n;
cin >> n;
vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];
int q;
cin >> q;
vector<int> l(q), r(q), x(q);
for (int i = 0; i < q; i++) cin >> l[i] >> r[i] >> x[i], l[i]--;
int64_t p = 1;
int64_t res = 0;
for (int i = 0; i < q; i++) (p *= 2) %= MOD;
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
vector<vector<int>> cntl(n + 1, vector<int>(n + 1));
vector<vector<int>> cntr(n + 1, vector<int>(n + 1));
vector<vector<int>> cntb(n + 1, vector<int>(n + 1));
for (int z = 0; z < q; z++) {
int a = x[z] >> i & 1, b = x[z] >> j & 1;
if (a && b) {
cntb[l[z]][l[z]]++;
cntb[l[z]][r[z]]--;
cntb[r[z]][l[z]]--;
cntb[r[z]][r[z]]++;
}
if (a) {
cntl[l[z]][r[z]]++;
cntl[l[z]][n + 1]--;
cntl[r[z]][r[z]]--;
cntl[r[z]][n + 1]--;
}
if (b) {
cntr[0][l[z]]++;
cntr[0][r[z]]--;
cntr[l[z]][l[z]]--;
cntr[l[z]][r[z]]++;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j < n; j++) {
cntl[i][j + 1] += cntl[i][j];
cntr[i][j + 1] += cntr[i][j];
cntb[i][j + 1] += cntb[i][j];
}
}
for (int j = 0; j <= n; j++) {
for (int i = 0; i < n; i++) {
cntl[i + 1][j] += cntl[i][j];
cntr[i + 1][j] += cntr[i][j];
cntb[i + 1][j] += cntb[i][j];
}
}
auto prod = [&](int a, int b) -> int64_t {
if (a == 0 && b == 1) return 0;
if (a == 0 && b == 0) return 2;
return 1;
};
for (int x = 0; x < n; x++) {
for (int y = x; y < n; y++) {
int64_t add = (1ll << (i + j)) * (x + 1) * (n - y) * (1 + (x != y));
add %= MOD;
int a = A[x] >> i & 1;
int b = A[y] >> j & 1;
for (int z = 0; z < 8; z++) {
if (((a ^ z ^ (z >> 1)) & 1) && ((b ^ z ^ (z >> 2)) & 1)) {
res += add * p % MOD * prod(cntb[x][y], z & 1) * prod(cntl[x][y], z >> 1 & 1) * prod(cntr[x][y], z >> 2 & 1);
res %= MOD;
}
}
}
}
}
}
res *= MOD + 1 >> 1;
res %= MOD;
res *= MOD + 1 >> 1;
res %= MOD;
res *= MOD + 1 >> 1;
res %= MOD;
cout << res;
}
Compilation message
xorsum.cpp: In function 'int32_t main()':
xorsum.cpp:84:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | res *= MOD + 1 >> 1;
| ~~~~^~~
xorsum.cpp:86:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | res *= MOD + 1 >> 1;
| ~~~~^~~
xorsum.cpp:88:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | res *= MOD + 1 >> 1;
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
1760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1558 ms |
12464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
