#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 9, N = 1003, M = 1e9 + 7, K = 7;
int a[N], pw[100005];
int cnt[N][N][K][K], cc[N][K];
// 0 -> 0 1
// 1 -> 1 0
// 2 -> 1 1
void add(int& a, int b) {
a += b;
if(a >= M) a -= M;
}
signed main()
{
IO_OP;
pw[0] = 1;
for(int i = 1; i < 100005; i++)
pw[i] = pw[i - 1] * 2 % M;
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
int q;
cin >> q;
for(int i = 0; i < q; i++) {
int l, r, x;
cin >> l >> r >> x;
for(int bit1 = 0; bit1 < K; bit1++) {
if(x >> bit1 & 1) {
cc[l][bit1]++;
cc[r + 1][bit1]--;
}
for(int bit2 = 0; bit2 < K; bit2++) {
int t1 = x >> bit1 & 1, t2 = x >> bit2 & 1;
if(t1 == 0 || t2 == 0) continue;
cnt[l][l][bit1][bit2]++;
cnt[l][r + 1][bit1][bit2]--;
cnt[r + 1][l][bit1][bit2]--;
cnt[r + 1][r + 1][bit1][bit2]++;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < K; j++)
cc[i][j] += cc[i - 1][j];
}
// TODO: change for loop order and see time
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int bit1 = 0; bit1 < K; bit1++) {
for(int bit2 = 0; bit2 < K; bit2++) {
cnt[i][j][bit1][bit2] += cnt[i - 1][j][bit1][bit2] +
cnt[i][j - 1][bit1][bit2] -
cnt[i - 1][j - 1][bit1][bit2];
}
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
int occ = i * (n - j + 1);
for(int bit1 = 0; bit1 < K; bit1++) {
for(int bit2 = 0; bit2 < K; bit2++) {
int mul = (ll(occ) << (bit1 + bit2)) % M;
if(i < j) mul = mul * 2 % M;
int c11 = cnt[i][j][bit1][bit2];
int c10 = cc[i][bit1] - c11;
int c01 = cc[j][bit2] - c11;
int c00 = q - c01 - c10 - c11;
int tt = 0;
int ways00 = 1, ways11 = 1;
int t1 = a[i] >> bit1 & 1, t2 = a[j] >> bit2 & 1;
if(t1 == 0 && t2 == 0) {
if(c01) ways00 = (ll) ways00 * pw[c01 - 1] % M;
if(c10) ways00 = (ll) ways00 * pw[c10 - 1] % M;
if(c01 == 0 || c10 == 0) ways11 = 0;
else {
ways11 = (ll) ways11 * pw[c01 - 1] % M;
ways11 = (ll) ways11 * pw[c10 - 1] % M;
}
} else if(t1 == 1 && t2 == 1) {
if(c01) ways11 = (ll) ways11 * pw[c01 - 1] % M;
if(c10) ways11 = (ll) ways11 * pw[c10 - 1] % M;
if(c01 == 0 || c10 == 0) ways00 = 0;
else {
ways00 = (ll) ways00 * pw[c01 - 1] % M;
ways00 = (ll) ways00 * pw[c10 - 1] % M;
}
} else if(t1 == 1 && t2 == 0) {
if(c01) ways00 = (ll) ways00 * pw[c01 - 1] % M;
if(c10) ways00 = (ll) ways00 * pw[c10 - 1] % M;
else ways00 = 0;
if(c01) ways11 = (ll) ways11 * pw[c01 - 1] % M;
else ways11 = 0;
if(c10) ways11 = (ll) ways11 * pw[c10 - 1] % M;
} else if(t1 == 0 && t2 == 1) {
if(c01) ways00 = (ll) ways00 * pw[c01 - 1] % M;
else ways00 = 0;
if(c10) ways00 = (ll) ways00 * pw[c10 - 1] % M;
if(c01) ways11 = (ll) ways11 * pw[c01 - 1] % M;
if(c10) ways11 = (ll) ways11 * pw[c10 - 1] % M;
else ways11 = 0;
} else throw;
if(c00) add(tt, (ll) ways11 * pw[c00 - 1] % M);
else add(tt, ways11);
if(c11) add(tt, (ll) ways00 * pw[c11 - 1] % M);
tt = (ll) tt * pw[c00] % M;
add(ans, (ll) tt * mul % M);
}
}
}
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
3052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
787 ms |
193260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
