#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)
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;
array<int,7> cnt;
Basis() : b{}, cnt{} {}
Basis & operator+=(int x) {
for(int y: b)
x = min(x, x^y);
if(x) {
b.pb(x);
for(int j = 0; j < 7; j++) if(x >> j & 1) ++cnt[j];
}
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 < n; i++) res[i] = res[i&-i] ^ res[i-(i&-i)];
return res;
}
size_t size() const { return b.size(); }
int calc(int x) {
// return sum(y^x for y in span());
int n = b.size();
int res = 0;
for(int j = 0; j < 7; j++) {
;
res += (1<<j) * (cnt[j] ? (1<<n-1) : (x>>j&1 ? 1 : 0));
}
return res;
}
};
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);
}
sort(all(evt));
map<int,int> mp;
int ans = 0;
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);
}
}
auto calc = [&](int i, int j) {
Basis A, B, C;
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;
}
}
debug(A.b, B.b, C.b);
int 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)) % MOD;
}
debug(res);
return 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: In member function 'int Basis::calc(int)':
xorsum.cpp:55:44: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
55 | res += (1<<j) * (cnt[j] ? (1<<n-1) : (x>>j&1 ? 1 : 0));
| ~^~
xorsum.cpp: In function 'int main()':
xorsum.cpp:72:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | for(auto &[l, r, x]: Qs) {
| ^
xorsum.cpp:84:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
84 | auto [_, v, x] = evt[j++];
| ^
xorsum.cpp:92:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
92 | for(auto [val, cnt]: mp)
| ^
xorsum.cpp: In lambda function:
xorsum.cpp:105:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
105 | for(auto [l, r, x]: Qs) {
| ^
| # |
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 |
Execution timed out |
2037 ms |
5856 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
677 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 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 |
- |
