#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
template<class T>
bool chmax(T &val, T nv) { return val < nv ? (val = nv, true) : false; }
template<class T>
bool chmin(T &val, T nv) { return nv < val ? (val = nv, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() {cerr << endl;}
template<class T1, class ...T2>
void kout (T1 v, T2 ...e) { cerr << v << ' ', kout(e...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 1005, p = 1e9 + 7, MAX_C = 128, MAX_Q = 100005;
//#define MAX_C 4
int n, v[MAX_N], res;
void add(int &a, int b) { a += b - p, a += (a >> 31) & p; }
int q;
vector<tuple<int,int,int>> allq;
int cnt2d[MAX_N][MAX_N], cnt1d[2][MAX_N], up2[MAX_Q]{1};
void putin2d(auto cnt, int mask) {
memset(cnt, 0, sizeof(cnt2d));
for (auto [l, r, x] : allq) if ((x & mask) == mask) {
++cnt[l][l], ++cnt[r+1][r+1];
--cnt[r+1][l], --cnt[l][r+1];
}
for (int i = 1;i <= n;++i) for (int j = 1;j <= n;++j)
cnt[i][j] += cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1];
}
void putin1d(auto cnt, int mask) {
memset(cnt, 0, sizeof(cnt1d[0]));
for (auto [l, r, x] : allq) if ((x & mask) == mask) {
++cnt[l], --cnt[r+1];
}
for (int i = 1;i <= n;++i)
cnt[i] += cnt[i-1];
}
void addup(int lm, int rm) {
putin1d(cnt1d[0], lm), putin1d(cnt1d[1], rm);
putin2d(cnt2d, lm | rm);
ll mul = lm * rm;
DE(lm, rm);
for (int i = 1;i <= n;++i)
for (int j = i + 1;j <= n;++j) {
int a = cnt1d[0][i], b = cnt1d[1][j], c = cnt2d[i][j];
int outside = q - (a + b - c);
a -= c, b -= c;
ll i0 = (a == 0 ? 1 : up2[a - 1]), i1 = (a == 0 ? 0 : up2[a - 1]);
ll j0 = (b == 0 ? 1 : up2[b - 1]), j1 = (b == 0 ? 0 : up2[b - 1]);
i0 = i0, i1 = i1;
j0 = j0, j1 = j1;
if (v[i] & lm) swap(i0, i1);
if (v[j] & rm) swap(j0, j1);
// if (v[i] & lm) assert(i1 == 1);
// if (v[j] & rm) assert(j1 == 1);
//assert(i0 + i1 == 1 && j0 + j1 == 1);
int c0 = (c == 0 ? 1 : up2[c - 1]), c1 = (c == 0 ? 0 : up2[c - 1]);
//assert(c0 == 1 && c1 == 0);
DE(i, j);
DE(i0, i1, j0, j1, c0, c1);
ll ij0 = i0 * j0 % p, ij1 = i1 * j1 % p;
DE(ij0, c1, '+', ij1, c0, '*', mul);
ll wei = up2[outside] * 2ll * i * (n - j + 1) * mul % p;
DE(i, j, wei, mul);
res += (ij0 * c1 + ij1 * c0) * wei % p;
}
res %= p;
}
int lstcnt[MAX_C][MAX_N];
void solvesq() {
for (auto [l, r, x] : allq)
++lstcnt[x][l], --lstcnt[x][r+1];
for (int c = 0;c < MAX_C;++c)
for (int i = 1;i <= n;++i)
lstcnt[c][i] += lstcnt[c][i-1];
for (int i = 1;i <= n;++i) {
int *A = new int[MAX_C]{}, *B = new int[MAX_C]{};
A[ v[i] ] = 1;
ll all = q;
for (int c = 0;c < MAX_C;++c) if (lstcnt[c][i]) {
all -= lstcnt[c][i];
fill(B, B + MAX_C, 0);
ll nw = up2[ lstcnt[c][i] - 1 ];
for (int x = 0;x < MAX_C;++x)
add(B[x], A[x] * nw % p), add(B[x ^ c], A[x] * nw % p);
swap(A, B);
}
all = up2[all];
ll wei = i * (n - i + 1) * all % p;
for (int c = 0;c < MAX_C;++c) if (A[c]) {
add(res, wei * (c * c) * A[c] % p);
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1;i <= n;++i)
cin >> v[i];
cin >> q;
allq.resize(q);
for (auto &[l, r, x] : allq)
cin >> l >> r >> x;
for (int i = 1;i <= q;++i)
up2[i] = up2[i-1] * 2 % p;
for (int lb = 1;lb < MAX_C;lb <<= 1)
for (int rb = 1;rb < MAX_C;rb <<= 1)
addup(lb, rb);
solvesq();
cout << res << '\n';
}
Compilation message
xorsum.cpp:39:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
39 | void putin2d(auto cnt, int mask) {
| ^~~~
xorsum.cpp:48:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
48 | void putin1d(auto cnt, int mask) {
| ^~~~
xorsum.cpp: In function 'void addup(int, int)':
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
18 | #define DE(...) 0
| ^
xorsum.cpp:62:2: note: in expansion of macro 'DE'
62 | DE(lm, rm);
| ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
18 | #define DE(...) 0
| ^
xorsum.cpp:91:4: note: in expansion of macro 'DE'
91 | DE(i, j);
| ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
18 | #define DE(...) 0
| ^
xorsum.cpp:93:4: note: in expansion of macro 'DE'
93 | DE(i0, i1, j0, j1, c0, c1);
| ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
18 | #define DE(...) 0
| ^
xorsum.cpp:97:4: note: in expansion of macro 'DE'
97 | DE(ij0, c1, '+', ij1, c0, '*', mul);
| ^~
xorsum.cpp:18:17: warning: statement has no effect [-Wunused-value]
18 | #define DE(...) 0
| ^
xorsum.cpp:101:4: note: in expansion of macro 'DE'
101 | DE(i, j, wei, mul);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 3 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 5 |
Correct |
10 ms |
4844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 3 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 5 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 6 |
Incorrect |
16 ms |
4972 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
7280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
508 ms |
5868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
4844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
4844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 3 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 5 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 6 |
Incorrect |
16 ms |
4972 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 3 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 5 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 6 |
Incorrect |
16 ms |
4972 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 3 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 5 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 6 |
Incorrect |
16 ms |
4972 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
