#pragma GCC optimize("Ofast")
#pragma GCC targat("avx2")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#ifdef local
#define debug(args...) qqbx(#args, args)
template <typename ...T> void qqbx(const char *s, T ...args) {
int cnt = sizeof...(T);
((std::cerr << "(" << s << ") = (") , ... , (std::cerr << args << (--cnt ? ", " : ")\n")));
}
#define TAK(args...) std::ostream &operator<<(std::ostream &O, args)
#define NIE(STL, BEG, END, OUT) template <typename ...T> TAK(std::STL<T...> v) \
{ int f=0; O << BEG; for(auto e: v) O << (f++ ? ", " : "") << OUT; return O << END; }
NIE(vector, "[", "]", e)
NIE(map, "{", "}", e.first << ',' << e.second)
template <typename T, size_t N> TAK(std::array<T,N> v) { return O << std::vector<T>(v.begin(), v.end()); }
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back
#define all(v) begin(v),end(v)
#define int ll
using namespace std;
using ll = long long;
using ld = double;
const int N = 100002, MOD = 1000000007;
const ll INF = 1e18;
const ld PI = acos(-1);
struct Basis {
vector<int> b;
int orsum;
Basis() : b(), orsum(0) {}
Basis & operator+=(int x) {
for(int y: b)
x = min(x, x^y);
if(x) {
b.pb(x);
orsum |= x;
}
return *this;
}
vector<int> span() const {
int n = b.size();
vector<int> res(1<<n);
for(int i = 0; i < n; i++) res[1<<i] = b[i];
for(int i = 1; i < (1<<n); i++) res[i] = res[i&-i] ^ res[i-(i&-i)];
return res;
}
int size() const { return b.size(); }
int calc(int x) {
// return sum(y^x for y in span());
if(b.empty()) return x;
// for(int y: span())
// res += y ^ x;
// return res;
int n = b.size();
int mask = 127 ^ orsum;
return orsum * (1<<n-1) + (127 ^ orsum) & (127 ^ x);
}
};
int cnt[1005][1005];
bitset<128> bA[1005][1005], bB[1005][1005], bC[1005][1005];
int query(int pre[][1005], int lx, int ly, int rx, int ry) {
return pre[rx][ry] - (lx ? pre[lx-1][ry] : 0) - (ly ? pre[rx][ly-1] : 0) + (lx && ly ? pre[lx-1][ly-1] : 0);
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, q;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
cin >> q;
vector<int> pw(q+1);
pw[0] = 1;
for(int i = 1; i <= q; i++) pw[i] = pw[i-1] * 2LL % MOD;
vector<tuple<int,int,int>> Qs(q);
vector<tuple<int,int,int>> evt;
for(auto &[l, r, x]: Qs) {
cin >> l >> r >> x;
--l, --r;
evt.pb(l, 1, x);
evt.pb(r+1, -1, x);
}
int ans = 0;
sort(all(evt));
map<int,int> mp;
for(int i = 0, j = 0; i < n; i++) {
while(j < q*2 && get<0>(evt[j]) <= i) {
auto [_, v, x] = evt[j++];
if(_ != i) continue;
mp[x] += v;
if(mp[x] == 0) mp.erase(x);
}
debug(mp);
Basis b;
// make basis
for(auto [val, cnt]: mp)
b += val;
// enumerate basis
int cnt = 1LL * pw[q - b.size()] * (i+1) * (n-i);
for(int x: b.span()) {
int ai = a[i] ^ x;
ans = (ans + 1LL * ai * ai * cnt) % MOD;
debug(ai, cnt);
}
}
for(int b = 0; b < 128; b++) {
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cnt[i][j] = 0;
for(auto [l, r, x]: Qs) if(x == b) cnt[l][r] += 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i) cnt[i][j] += cnt[i-1][j];
if(j) cnt[i][j] += cnt[i][j-1];
if(i && j) cnt[i][j] -= cnt[i-1][j-1];
}
}
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
if(query(cnt, 0, j, i, n-1))
bC[i][j][b] = true;
if(query(cnt, 0, i, i, j-1))
bA[i][j][b] = true;
if(query(cnt, i+1, j, j, n-1))
bB[i][j][b] = true;
}
}
}
auto calc = [&](int i, int j) {
/*
for(auto [l, r, x]: Qs) {
if(l <= i && j <= r) {
C += x;
} else if(l <= i && r >= i && r < j) {
A += x;
} else if(l > i && l <= j && r >= j) {
debug(l, r, i, j);
B += x;
}
}
*/
Basis A, B, C;
for(int b = 0; b < 128; b++) {
if(bA[i][j][b])
A += b;
if(bB[i][j][b])
B += b;
if(bC[i][j][b])
C += b;
}
ll res = 0;
for(int x: C.span()) {
int ai = a[i] ^ x, aj = a[j] ^ x;
debug(ai, aj);
res = (res + 1LL * A.calc(ai) * B.calc(aj));
}
debug(res);
return 1LL * res * pw[q - (C.size() + A.size() + B.size())] % MOD;
};
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
int cnt = 2 * (i+1) * (n-j);
ans = (ans + 1LL * calc(i, j) * cnt) % MOD;
}
}
cout << ans << '\n';
}
Compilation message
xorsum.cpp:2: warning: ignoring #pragma GCC targat [-Wunknown-pragmas]
2 | #pragma GCC targat("avx2")
|
xorsum.cpp:3: warning: ignoring #pragma loop_opt [-Wunknown-pragmas]
3 | #pragma loop_opt(on)
|
xorsum.cpp: In member function 'll Basis::calc(ll)':
xorsum.cpp:61:29: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
61 | return orsum * (1<<n-1) + (127 ^ orsum) & (127 ^ x);
| ~^~
xorsum.cpp:61:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
61 | return orsum * (1<<n-1) + (127 ^ orsum) & (127 ^ x);
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
xorsum.cpp:60:13: warning: unused variable 'mask' [-Wunused-variable]
60 | int mask = 127 ^ orsum;
| ^~~~
xorsum.cpp: In function 'int main()':
xorsum.cpp:82:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
82 | for(auto &[l, r, x]: Qs) {
| ^
xorsum.cpp:94:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
94 | auto [_, v, x] = evt[j++];
| ^
xorsum.cpp:102:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
102 | for(auto [val, cnt]: mp)
| ^
xorsum.cpp:115:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | for(auto [l, r, x]: Qs) if(x == b) cnt[l][r] += 1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
9824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1235 ms |
33312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
