#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
namespace modulofunc{
const int mod = 1e9+7;
int add(int x, int y) {
ll temp = x+y;
if (temp >= mod) temp -= mod;
return temp;
}
void ad(int &x, int y) {
x = add(x, y);
}
int sub(int x, int y) {
ll temp = x-y;
if (temp < 0) temp += mod;
return temp;
}
int mul(int x, int y) {
return 1LL*x*y%mod;
}
int binpow(int x, int k) {
int res = 1;
while (k > 0) {
if (k&1) res = mul(res, x);
k >>= 1;
x = mul(x, x);
}
return res;
}
}
using namespace modulofunc;
const int maxn = 1005, lg = 7, maxq = 1e5+5;
int n, a[maxn], q;
int pw2[maxq];
int d[maxn][lg];
vector<int> inc[maxn][lg][lg]; //case 1
int d1[maxn][lg][lg]; //-=
int ans = 0;
void prep() {
//2^i
pw2[0] = 1;
for (int i = 1; i < maxq; i++) {
pw2[i] = mul(pw2[i-1], 2);
}
}
int sumcomb(int n, bool j){
if (n == 0) return (j == 0);
return pw2[n-1];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
prep();
//input
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
//tach bit from updates -> inc
memset(d, 0, sizeof(d));
cin >> q;
for (int i = 1; i <= q; i++)
{
int l, r, x;
cin >> l >> r >> x;
for (int j = 0; j < lg; j++) {
if (BITj(x, j)) {
// cout << j << ' ';
d[l][j]++;
d[r+1][j]--;
for (int j2 = 0; j2 < lg; j2++) {
if (BITj(x, j2)) {
inc[r][j][j2].pb(l);
}
}
}
}
}
// cout << "\n";
//precal d ->2, 3
//cnt updates -> i
for (int i = 1; i <= n; i++) {
for (int j = 0; j < lg; j++) {
d[i][j] += d[i-1][j];
}
}
// for (int j = 0; j < lg; j++) {
// for (int i = 1; i <= n; i++) {
// cout << d[i][j] << ' ';
// }
// cout << "\n";
// }
//i: n-> 1
memset(d1, 0, sizeof(d1));
int allsum[lg][lg], cursum[lg][lg];
memset(allsum, 0, sizeof(allsum));
memset(cursum, 0, sizeof(cursum));
for (int i = n; i; i--) {
//cal i
for (int x = 0; x < lg; x++) {
int valbit = pw2[2*x];
int valq = mul(pw2[q-d[i][x]], sumcomb(d[i][x], BITj(a[i],x)^1));
int valseg = mul(i, n-i+1);
ad(ans, mul(mul(valbit, valq), valseg));
// int temp = mul(mul(valbit, valq), valseg);
// if (temp > 0) {
// cout << "case i: " << i << ' ' << x << ' ' << temp << "\n";
// }
//allsumi
for (int y = 0; y < lg; y++) {
for (int id : inc[i][x][y]) {
++allsum[x][y];
d1[id][x][y]++;
}
cursum[x][y] = allsum[x][y];
}
}
//moi cap i, j: i -> 1
for (int j = i; j; j--) {
//cnt updates i and j
//every bit x y
for (int x = 0; x < lg; x++) {
for (int y = 0; y < lg; y++) {
if (i == j && x <= y) continue;
int valbit, valq, valseg;
int case1 = cursum[x][y];
int case2 = d[j][y]-case1;
int case3 = d[i][x]-case1;
valbit = pw2[x+y+1];
bool biti = BITj(a[i], x), bitj = BITj(a[j], y);
valq = mul(mul(sumcomb(case3, biti^1), sumcomb(case2, bitj^1)), sumcomb(case1, 0)); //1 - 1
ad(valq, mul(mul(sumcomb(case3, biti), sumcomb(case2, bitj)), sumcomb(case1, 1))); //0 - 0
valq = mul(valq, pw2[q-case1-case2-case3]); //case4
valseg = mul(j, n-i+1);
ad(ans, mul(mul(valbit, valq), valseg));
// int temp = mul(mul(valbit, valq), valseg);
// if (temp > 0) {
// cout << "case bit: " << j << ' ' << i << ' ' << y << ' ' << x << "\n";
// cout << case1 << ' ' << case2 << ' ' << case3 << ' ' << valbit << ' ' << valq << ' ' << valseg << ' ' << temp << "\n";
// cout << bitj << ' ' << biti << ' ';
// cout << mul(mul(sumcomb(case3, biti^1), sumcomb(case2, bitj^1)), sumcomb(case1, 0)) << ' ';
// cout << mul(mul(sumcomb(case3, biti), sumcomb(case2, bitj)), sumcomb(case1, 1)) << ' ';
// cout << pw2[q-case1-case2-case3] << "\n";
// }
//reset
cursum[x][y] -= d1[j][x][y];
}
}
//contribute to the sum
}
}
cout << ans;
}
/*
2
1 3
1
1 2 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2128 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2296 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2128 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2128 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2296 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2128 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
14160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
469 ms |
2632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2128 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2296 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2128 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2128 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2296 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2128 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2128 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2296 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2128 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
