#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()
#define int long long
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;
}
signed 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);
vector<int> pw2(1e3 + 10);
pw2[0] = 1;
for (int i = 1; i < 1e3 + 10; i++){
pw2[i] = mul(pw2[i - 1], 2);
}
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 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];
if (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][k][0] = add(dp1[s ^ x][k][0], mul(pw2[cnt - 1], dp0[s][k][0]));
dp1[s ^ x][k][1] = add(dp1[s ^ x][k][1], mul(pw2[cnt - 1], dp0[s][k][1]));
// dp1[s][k][0] = add(dp1[s][k][0], mul(sub(pw2[cnt - 1], 1), dp0[s][k][0]));
// dp1[s][k][1] = add(dp1[s][k][1], mul(sub(pw2[cnt - 1], 1), dp0[s][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 |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
53 ms |
440 KB |
Output is correct |
| 3 |
Correct |
202 ms |
428 KB |
Output is correct |
| 4 |
Correct |
197 ms |
432 KB |
Output is correct |
| 5 |
Incorrect |
196 ms |
432 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
53 ms |
440 KB |
Output is correct |
| 3 |
Correct |
202 ms |
428 KB |
Output is correct |
| 4 |
Correct |
197 ms |
432 KB |
Output is correct |
| 5 |
Incorrect |
196 ms |
432 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2070 ms |
5860 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1692 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1692 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
53 ms |
440 KB |
Output is correct |
| 3 |
Correct |
202 ms |
428 KB |
Output is correct |
| 4 |
Correct |
197 ms |
432 KB |
Output is correct |
| 5 |
Incorrect |
196 ms |
432 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
53 ms |
440 KB |
Output is correct |
| 3 |
Correct |
202 ms |
428 KB |
Output is correct |
| 4 |
Correct |
197 ms |
432 KB |
Output is correct |
| 5 |
Incorrect |
196 ms |
432 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
53 ms |
440 KB |
Output is correct |
| 3 |
Correct |
202 ms |
428 KB |
Output is correct |
| 4 |
Correct |
197 ms |
432 KB |
Output is correct |
| 5 |
Incorrect |
196 ms |
432 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
