#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];
}
}
vector<vector<vector<int>>> pref((1 << 7), vector<vector<int>>(n + 1, vector<int>(n + 1)));
for (int i = 0; i < q; i++){
pref[req[i][2]][req[i][0]][req[i][1]]++;
}
for (int x = 0; x < (1 << 7); x++){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
pref[x][i][j] += pref[x][i][j - 1];
}
}
for (int j = 1; j <= n; j++){
for (int i = 1; i <= n; i++){
pref[x][i][j] += pref[x][i - 1][j];
}
}
}
function<int(int, int, int, int, int)> count = [&](int x, int i1, int j1, int i2, int j2){
if (i1 > i2 || j1 > j2){
return 0;
}
return pref[x][i2][j2] - pref[x][i1 - 1][j2] - pref[x][i2][j1 - 1] + pref[x][i1 - 1][j1 - 1];
};
int res = 0;
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 s = 0; s < (1 << 7); s++){
dp1 = dp0;
for (int h = 0; h < (1 << 7); h++){
int x = 0;
int y = 0;
int cnt = 0;
// y = 0;
for (int k = 0; k < 7; k++){
// x = 0, y = 0
x = 0;
cnt = count(s, 1, 1, i - 1, i - 1) +
count(s, i + 1, i + 1, j - 1, j - 1) +
count(s, j + 1, j + 1, n, n);
dp1[h ^ x][k][0] = add(dp1[h ^ x][k][0], mul(dp0[h][k][0], cnt));
dp1[h ^ x][k][1] = add(dp1[h ^ x][k][1], mul(dp0[h][k][1], cnt));
// x = s, y = 0;
x = s;
cnt = count(s, 1, i, i, j - 1);
dp1[h ^ x][k][0] = add(dp1[h ^ x][k][0], mul(dp0[h][k][0], cnt));
dp1[h ^ x][k][1] = add(dp1[h ^ x][k][1], mul(dp0[h][k][1], cnt));
}
for (int k = 0; k < 7; k++){
if (s & (1 << k)){
swap(dp0[h][k][0], dp0[h][k][1]);
}
// x = 0, y = s
cnt = count(s, i + 1, j, j, n);
x = 0;
dp1[h ^ x][k][0] = add(dp1[h ^ x][k][0], mul(dp0[h][k][0], cnt));
dp1[h ^ x][k][1] = add(dp1[h ^ x][k][1], mul(dp0[h][k][1], cnt));
// x = s, y = s;
cnt = count(s, 1, j, i, n);
x = s;
dp1[h ^ x][k][0] = add(dp1[h ^ x][k][0], mul(dp0[h][k][0], cnt));
dp1[h ^ x][k][1] = add(dp1[h ^ x][k][1], mul(dp0[h][k][1], cnt));
if (s & (1 << k)){
swap(dp0[h][k][0], dp0[h][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;
}
Compilation message
xorsum.cpp: In function 'int main()':
xorsum.cpp:94:29: warning: unused variable 'y' [-Wunused-variable]
94 | int y = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
340 KB |
Output is correct |
| 2 |
Correct |
108 ms |
452 KB |
Output is correct |
| 3 |
Correct |
416 ms |
532 KB |
Output is correct |
| 4 |
Correct |
428 ms |
528 KB |
Output is correct |
| 5 |
Incorrect |
415 ms |
528 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
340 KB |
Output is correct |
| 2 |
Correct |
108 ms |
452 KB |
Output is correct |
| 3 |
Correct |
416 ms |
532 KB |
Output is correct |
| 4 |
Correct |
428 ms |
528 KB |
Output is correct |
| 5 |
Incorrect |
415 ms |
528 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2076 ms |
11476 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
121 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2073 ms |
1060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2073 ms |
1060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
340 KB |
Output is correct |
| 2 |
Correct |
108 ms |
452 KB |
Output is correct |
| 3 |
Correct |
416 ms |
532 KB |
Output is correct |
| 4 |
Correct |
428 ms |
528 KB |
Output is correct |
| 5 |
Incorrect |
415 ms |
528 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
340 KB |
Output is correct |
| 2 |
Correct |
108 ms |
452 KB |
Output is correct |
| 3 |
Correct |
416 ms |
532 KB |
Output is correct |
| 4 |
Correct |
428 ms |
528 KB |
Output is correct |
| 5 |
Incorrect |
415 ms |
528 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
340 KB |
Output is correct |
| 2 |
Correct |
108 ms |
452 KB |
Output is correct |
| 3 |
Correct |
416 ms |
532 KB |
Output is correct |
| 4 |
Correct |
428 ms |
528 KB |
Output is correct |
| 5 |
Incorrect |
415 ms |
528 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
