#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;
}
int naive(vector<int> a, vector<vector<int>> req){
int n = a.size() - 1;
int q = req.size();
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 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));
}
}
}
}
return res;
}
vector<vector<vector<int>>> pref;
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];
}
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;
int cntbit = 6;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
assert(a[i] < 32);
// if (a[i]){
// cntbit = max(cntbit, (int)(32 - __builtin_clz(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];
}
assert(req[id][2] < 32);
// if (req[id][2]){
// cntbit = max(cntbit, (int)(32 - __builtin_clz(req[id][2])));
// }
}
#ifdef ON_PC
cout << naive(a, req) << "\n";
#endif
pref = vector<vector<vector<int>>>((1 << cntbit), 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 << cntbit); 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];
}
}
}
int res = 0;
for (int i = 1; i <= n; i++){
for (int j = i; j <= n; j++){
vector<vector<vector<int>>> dp0((1 << cntbit), vector<vector<int>>(cntbit, vector<int>(2)));
vector<vector<vector<int>>> dp1((1 << cntbit), vector<vector<int>>(cntbit, vector<int>(2)));
for (int k = 0; k < cntbit; k++){
dp0[a[i]][k][bool(a[j] & (1 << k))]++;
}
vector<vector<vector<int>>> qcnt((1 << cntbit), vector<vector<int>>(2, vector<int>(2)));
for (int s = 0; s < (1 << cntbit); s++){
qcnt[s][0][0] = 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);
qcnt[s][0][1] = count(s, i + 1, j, j, n);
qcnt[s][1][0] = count(s, 1, i, i, j - 1);
qcnt[s][1][1] = count(s, 1, j, i, n);
}
// 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 << cntbit); 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 << cntbit); s++){
for (int k = 0; k < cntbit; 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]));
if (y & (1 << k)){
swap(dp0[s][k][0], 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]));
}
}
}
dp1.swap(dp0);
}
}
}
int segcnt = mul(i, n - j + 1);
int t = mul(segcnt, 1 + (i != j));
for (int s = 0; s < (1 << cntbit); s++){
for (int k = 0; k < cntbit; 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 |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
15 ms |
404 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
15 ms |
404 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2089 ms |
8624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
496 ms |
688 KB |
Output is correct |
| 2 |
Correct |
485 ms |
692 KB |
Output is correct |
| 3 |
Correct |
489 ms |
684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
496 ms |
688 KB |
Output is correct |
| 2 |
Correct |
485 ms |
692 KB |
Output is correct |
| 3 |
Correct |
489 ms |
684 KB |
Output is correct |
| 4 |
Correct |
722 ms |
960 KB |
Output is correct |
| 5 |
Correct |
740 ms |
980 KB |
Output is correct |
| 6 |
Correct |
740 ms |
980 KB |
Output is correct |
| 7 |
Correct |
754 ms |
960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
15 ms |
404 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
15 ms |
404 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
15 ms |
404 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
