Something about the XOR problem
Read this article first
Let’s look at a classic example first
XOR sequence
Solution
C++ code is as follows (first type)
#include <bits/stdc + + .h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\\
";
#define no std::cout << "NO\\
";
void solve() {<!-- -->
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i + + ) {<!-- -->
std::cin >> a[i];
}
int ans = 0;
for (int u = 0; u < 31; u + + ) {<!-- -->
int s = 0,m = 0;
for (int i = 1; i <= n; i + + ) {<!-- -->
if (a[i] >> u & amp; 1) {<!-- -->
s = i - s;
}
m + = s;
}
ans + = (1 << u) * m;
}
std::cout << ans << "\\
";
}
signed main() {<!-- -->
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {<!-- -->
solve();
}
return 0;
}
C++ code is as follows (second type)
#include <bits/stdc + + .h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\\
";
#define no std::cout << "NO\\
";
void solve() {<!-- -->
int n;
std::cin >> n;
std::vector<int> s(n + 1);
for (int i = 1; i <= n; i + + ) {<!-- -->
int x;
std::cin >> x;
s[i] = s[i - 1] ^ x;
}
std::vector<int> cnt0(31),cnt1(31);
int ans = 0;
for (int i = 0; i <= n; i + + ) {<!-- -->
for (int u = 0; u < 31; u + + ) {<!-- -->
if (s[i] >> u & amp; 1) {<!-- -->
ans + = (1 << u) * cnt0[u];
cnt1[u] + + ;
} else {<!-- -->
ans + = (1 << u) * cnt1[u];
cnt0[u] + + ;
}
}
}
std::cout << ans << "\\
";
}
signed main() {<!-- -->
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {<!-- -->
solve();
}
return 0;
}
See here to calculate the number of intervals
C++ Code 3
#include <bits/stdc + + .h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\\
";
#define no std::cout << "NO\\
";
void solve() {<!-- -->
int n;
std::cin >> n;
std::vector<int> s(n + 1);
for (int i = 1; i <= n; i + + ) {<!-- -->
int x;
std::cin >> x;
s[i] = s[i - 1] ^ x;
}
std::vector<int> cnt0(31,1),cnt1(31);
int ans = 0;
for (int u = 0; u < 31; u + + ) {<!-- -->
cnt0[u] = 1;
for (int i = 1; i <= n; i + + ) {<!-- -->
if (s[i] >> u & amp; 1) {<!-- -->
cnt1[u] + + ;
} else {<!-- -->
cnt0[u] + + ;
}
}
ans + = (1 << u) * (cnt0[u] * cnt1[u]);
}
std::cout << ans << "\\
";
}
signed main() {<!-- -->
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {<!-- -->
solve();
}
return 0;
}
Exercise (classic questions)
Portal
XOR + tree (change root DP)
Main video begins
Question link
Compared with the above question, this question has one more (r – l + 1); when broken down, it is r * f(l,r) – (l – 1) * f(l,r); Each bit of f(l,r) corresponds to the number of intervals in the i-th row of j. Then * i is enough for each calculation. The left side can be expressed as i * res[i][j], and the right side can be expressed as i * res[i][j]. Then record the l – 1 that appears at each position
Note that the above code 2 is used as an example. Code 1 is not easy to calculate l – 1. Code 3 is a space-optimized version of code 2
The code is as follows
#include <bits/stdc + + .h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\\
";
#define no std::cout << "NO\\
";
template<class T>
T power(T a, i64 b) {<!-- -->
T res = 1;
for (; b; b /= 2, a *= a) {<!-- -->
if (b % 2) {<!-- -->
res *= a;
}
}
return res;
}
template<int P>
struct MInt {<!-- -->
int x;
MInt() : x{<!-- -->} {<!-- -->}
MInt(i64 x) : x{<!-- -->norm(x % P)} {<!-- -->}
int norm(int x) {<!-- -->
if (x < 0) {<!-- -->
x + = P;
}
if (x >= P) {<!-- -->
x -= P;
}
return x;
}
int val() const {<!-- -->
return x;
}
MInt operator-() const {<!-- -->
MInt res;
res.x = norm(P - x);
return res;
}
MInt inv() const {<!-- -->
assert(x != 0);
return power(*this, P - 2);
}
MInt & amp;operator*=(const MInt & amp;rhs) {<!-- -->
x = 1LL * x * rhs.x % P;
return *this;
}
MInt & amp;operator + =(const MInt & amp;rhs) {<!-- -->
x = norm(x + rhs.x);
return *this;
}
MInt & amp;operator-=(const MInt & amp;rhs) {<!-- -->
x = norm(x - rhs.x);
return *this;
}
MInt & amp;operator/=(const MInt & amp;rhs) {<!-- -->
return *this *= rhs.inv();
}
friend MInt operator*(const MInt & amp;lhs, const MInt & amp;rhs) {<!-- -->
MInt res = lhs;
res *= rhs;
return res;
}
friend MInt operator + (const MInt & amp;lhs, const MInt & amp;rhs) {<!-- -->
MInt res = lhs;
res + = rhs;
return res;
}
friend MInt operator-(const MInt & amp;lhs, const MInt & amp;rhs) {<!-- -->
MInt res = lhs;
res -= rhs;
return res;
}
friend MInt operator/(const MInt & amp;lhs, const MInt & amp;rhs) {<!-- -->
MInt res = lhs;
res /= rhs;
return res;
}
friend std::istream & amp;operator>>(std::istream & amp;is, MInt & amp;a) {<!-- -->
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend std::ostream & amp;operator<<(std::ostream & amp;os, const MInt & amp;a) {<!-- -->
return os << a.val();
}
};
constexpr int P = 998244353;
using Z = MInt<p>;
void solve() {<!-- -->
int n;
std::cin >> n;
std::vector<int> s(n + 1);
for (int i = 1; i <= n; i + + ) {<!-- -->
int x;
std::cin >> x;
s[i] = s[i - 1] ^ x;
}
std::vector cnt(30,std::vector<int>(2));
std::vector res(30,std::vector<int>(2));
Z ans = 0;
for (int i = 0; i <= n; i + + ) {<!-- -->
for (int u = 0; u < 30; u + + ) {<!-- -->
if (s[i] >> u & amp; 1) {<!-- -->
ans + = Z(1 << u) * (res[u][0] * i - cnt[u][0]);
res[u][1] + + ;
cnt[u][1] + = i;
} else {<!-- -->
ans + = Z(1 << u) * (res[u][1] * i - cnt[u][1]);
res[u][0] + + ;
cnt[u][0] + = i;
}
}
}
std::cout << ans << "\\
";
}
signed main() {<!-- -->
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {<!-- -->
solve();
}
return 0;
}
The prefix XOR is 1, which means that this interval has an odd number of 1’s. Then the prefix interval ending with the current number has cnt / 2 + 1 number that satisfies the interval XOR of 1 and cnt is 1 (for example, 111, There are 2 intervals ending with at least 1)
The prefix XOR is 0, which means that this interval has an even number of 1s. Then the prefix interval ending with the current number has cnt / 2 numbers that satisfy the interval XOR of 1 and cnt is 1 (for example, 101, with the most There is 1 interval ending in 1)
The significance of the res array is to record the number of odd-even intervals
Last point
Summary of XOR interval problems