#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))]++;
}
vector<vector<vector<int>>> qcnt((1 << 7), vector<vector<int>>(2, vector<int>(2)));
for (int w = 0; w < q; w++){
qcnt[req[w][2]][(req[w][0] <= i && i <= req[w][1])][(req[w][0] <= j && j <= req[w][1])]++;
}
for (int h = 0; h < (1 << 7); h++){
for (int i1 = 0; i1 <= 1; i1++){
for (int i2 = 0; i2 <= 1; i2++){
dp1 = dp0;
int x = h * i1;
int y = h * i2;
int cnt = qcnt[h][i1][i2];
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], mul(cnt, dp0[s][k][0]));
dp1[s ^ x][k][1] = add(dp1[s ^ x][k][1], mul(cnt, dp0[s][k][1]));
if (y & (1 << k)){
swap(dp0[s][k][0], dp0[s][k][1]);
}
}
}
if (cnt > 1){
cnt--;
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 ^ x][k][0] = add(dp1[s ^ x ^ x][k][0], mul(cnt, dp0[s ^ x][k][0]));
dp1[s ^ x ^ x][k][1] = add(dp1[s ^ x ^ x][k][1], mul(cnt, dp0[s ^ x][k][1]));
if (y & (1 << k)){
swap(dp0[s][k][0], 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));
}
}
}
}
cout << res << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
340 KB |
Output is correct |
| 2 |
Correct |
103 ms |
444 KB |
Output is correct |
| 3 |
Correct |
359 ms |
420 KB |
Output is correct |
| 4 |
Correct |
359 ms |
424 KB |
Output is correct |
| 5 |
Incorrect |
383 ms |
424 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
340 KB |
Output is correct |
| 2 |
Correct |
103 ms |
444 KB |
Output is correct |
| 3 |
Correct |
359 ms |
420 KB |
Output is correct |
| 4 |
Correct |
359 ms |
424 KB |
Output is correct |
| 5 |
Incorrect |
383 ms |
424 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2074 ms |
5844 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2093 ms |
468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2099 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2099 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
340 KB |
Output is correct |
| 2 |
Correct |
103 ms |
444 KB |
Output is correct |
| 3 |
Correct |
359 ms |
420 KB |
Output is correct |
| 4 |
Correct |
359 ms |
424 KB |
Output is correct |
| 5 |
Incorrect |
383 ms |
424 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
340 KB |
Output is correct |
| 2 |
Correct |
103 ms |
444 KB |
Output is correct |
| 3 |
Correct |
359 ms |
420 KB |
Output is correct |
| 4 |
Correct |
359 ms |
424 KB |
Output is correct |
| 5 |
Incorrect |
383 ms |
424 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
340 KB |
Output is correct |
| 2 |
Correct |
103 ms |
444 KB |
Output is correct |
| 3 |
Correct |
359 ms |
420 KB |
Output is correct |
| 4 |
Correct |
359 ms |
424 KB |
Output is correct |
| 5 |
Incorrect |
383 ms |
424 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
