#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define range(i, n) for (int i = 0; i < (n); ++i)
#define ar array
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
//using namespace __gnu_pbds;
const ll INF = 1e18 + 5;
const int INFi = 1e9;
const int maxN = 1e7 + 1500;
const int md2 = 998244353;
const int md = 1e9 + 7;
int add(int a, int b) {
if (a + b >= md) return a + b - md;
return a + b;
}
int sub(int a, int b) {
if (a - b < 0) return a - b + md;
return a - b;
}
int mul(int a, int b) {
return (1ll * a * b) % md;
}
int binpow(int a, int b) {
if (b <= 0) return 1;
if (b % 2) return mul(a, binpow(a, b - 1));
int m = binpow(a, b / 2);
return mul(m, m);
}
int rev(int a) {
return binpow(a, md - 2);
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
range(i, n) cin >> a[i];
int q;
cin >> q;
vector<int> st2(q + 5);
st2[0] = 1;
for (int i = 1; i < st2.size(); ++i) st2[i] = mul(st2[i - 1], 2);
vector<ar<int, 3>> b(q);
range(i, q) range(j, 3) cin >> b[i][j];
int ans = 0;
sort(all(b));
range(b1, 8) {
range(b2, 8) {
int result = 0;
vector<vector<ar<int, 4>>> Cnt(n + 5, vector<ar<int, 4>>(n + 5));
auto ADD = [&](int x1, int y1, int x2, int y2, int m) {
Cnt[x1][y1][m] += 1;
Cnt[x1][y1][0] -= 1;
Cnt[x2 + 1][y2 + 1][m] += 1;
Cnt[x2 + 1][y2 + 1][0] -= 1;
Cnt[x1][y2 + 1][m] -= 1;
Cnt[x2 + 1][y1][m] -= 1;
Cnt[x1][y2 + 1][0] += 1;
Cnt[x2 + 1][y1][0] += 1;
};
range(i, q) {
auto[l, r, x] = b[i];
Cnt[0][0][0]++;
if ((x & (1 << b1)) && (x & (1 << b2))) {
ADD(l - 1, l - 1, r - 1, r - 1, 3);
ADD(l - 1, r, r - 1, n, 1);
if (l != 1) ADD(0, l - 1, l - 2, r - 1, 2);
} else if (x & (1 << b1)) {
ADD(l - 1, 0, r - 1, n, 1);
} else if (x & (1 << b2)) {
ADD(0, l - 1, n, r - 1, 2);
}
}
range(i, n) {
range(j, n) {
range(e, 4) {
if (i) Cnt[i][j][e] += Cnt[i - 1][j][e];
if (j) Cnt[i][j][e] += Cnt[i][j - 1][e];
if (i && j) Cnt[i][j][e] += Cnt[i - 1][j - 1][e];
}
}
}
range(i, n) {
for (int j = i; j < n; ++j) {
auto cnt = Cnt[i][j];
int cur = 0;
if (cnt[1] && cnt[2]) {
cur = st2[q - 2];
} else if (cnt[1] && cnt[3]) {
cur = st2[q - 2];
} else if (cnt[2] && cnt[3]) {
cur = st2[q - 2];
} else if (cnt[1]) {
if (a[j] & (1 << b2)) {
cur = st2[q - 1];
}
} else if (cnt[2]) {
if (a[i] & (1 << b1)) {
cur = st2[q - 1];
}
} else if (cnt[3]) {
int A = (a[i] >> b1) & 1;
int B = (a[j] >> b2) & 1;
if (A == B) {
cur = st2[q - 1];
}
} else if (((a[i] >> b1) & 1) && ((a[j] >> b2) & 1)) {
cur = st2[q];
}
result = add(result, mul(1 + (i != j), mul(cur, mul(i + 1, n - j))));
}
}
ans = add(ans, mul(result, 1 << (b1 + b2)));
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(15) << fixed;
int tests = 1;
//cin >> tests;
range(_, tests) {
solve();
}
return 0;
}
Compilation message
xorsum.cpp: In function 'void solve()':
xorsum.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 1; i < st2.size(); ++i) st2[i] = mul(st2[i - 1], 2);
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
16488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
