A BIT of an Inequality
题目描述
给你一个数组 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an 。求这样的图元( x , y , z x, y, z x,y,z )的个数:
- 1 ≤ x ≤ y ≤ z ≤ n 1 \leq x \leq y \leq z \leq n 1≤x≤y≤z≤n , 和
- f ( x , y ) ⊕ f ( y , z ) > f ( x , z ) f(x, y) \oplus f(y, z) > f(x, z) f(x,y)⊕f(y,z)>f(x,z) .
我们定义 f ( l , r ) = a l ⊕ a l + 1 ⊕ … ⊕ a r f(l, r) = a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r} f(l,r)=al⊕al+1⊕…⊕ar ,其中 ⊕ \oplus ⊕ 表示 bitwise XOR。
输入描述
第一行包含一个整数 t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104 ) - 测试用例数。
每个测试用例的第一行包含一个整数 n n n ( 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105 )。
每个测试用例的第二行包含 n n n 个整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an ( 1 ≤ a i ≤ 1 0 9 1 \leq a_i \leq 10^9 1≤ai≤109 )。
保证所有测试用例中 n n n 的总和不超过 1 0 5 10^5 105 。
输出描述
对于每个测试用例,在一行中输出一个整数 – 描述的图元的组数。
样例输入
3
3
6 2 4
1
3
5
7 3 7 2 1
样例输出
4
0
16
原题
CF——传送门
思路
显然根据异或运算的交换律,
f
(
x
,
y
)
⊕
f
(
y
,
z
)
>
f
(
x
,
z
)
f(x, y) \oplus f(y, z) > f(x, z)
f(x,y)⊕f(y,z)>f(x,z) 等价于
f
(
x
,
z
)
⊕
a
y
>
f
(
x
,
z
)
f(x, z) \oplus a_y > f(x, z)
f(x,z)⊕ay>f(x,z)。那么,问题就可以转化为对于
a
1
a_1
a1 到
a
n
a_n
an 的每个
a
i
a_i
ai,其与
f
(
x
,
z
)
f(x, z)
f(x,z) 进行异或运算是否会使结果变小。如果能使结果变小,则将该方案统计到答案中。而对于异或后对结果的影响,我们只需要考虑
a
i
a_i
ai 的最高位的 1,若该位在左式即
f
(
x
,
y
)
⊕
f
(
y
,
z
)
f(x, y) \oplus f(y, z)
f(x,y)⊕f(y,z) 中的异或结果为 1,则将该方案统计进答案中。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 6;
const int maxbit = 30;
// 第i个元素,第j+1个bit位,前缀以及后缀异或结果为k(0或1)
int prefix[maxn][maxbit][2]; // 该条件下 包含第i-1个元素的前缀的个数
int suffix[maxn][maxbit][2]; // 该条件下 包含第i+1个元素的后缀的个数
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
// dp转移
for (int j = 0; j < 30; j++)
{
// 初始化
prefix[0][j][0] = 0;
prefix[0][j][1] = 0;
suffix[n + 1][j][0] = 0;
suffix[n + 1][j][1] = 0;
for (int i = 1; i <= n; i++)
{
int bit = (a[i] >> j) & 1; // 第j+1个bit位是1或是0
for (int k = 0; k <= 1; k++)
{
prefix[i][j][k] = (bit == k) + prefix[i - 1][j][k ^ bit];
}
}
for (int i = n; i >= 1; i--)
{
int bit = (a[i] >> j) & 1; // 第j+1个bit位是1或是0
for (int k = 0; k <= 1; k++)
{
suffix[i][j][k] = (bit == k) + suffix[i + 1][j][k ^ bit];
}
}
}
ll ans = 0; // 统计个数
for (int i = 1; i <= n; i++)
{
int highbit = -1; // 当前元素bit位为1的最高位置
for (int j = 0; j < 30; j++)
{
if ((a[i] >> j) & 1)
highbit = j;
}
ans += 1LL * prefix[i - 1][highbit][1] * (suffix[i + 1][highbit][0] + 1);
ans += 1LL * (prefix[i - 1][highbit][0] + 1) * suffix[i + 1][highbit][1];
}
cout << ans << '\n';
}
return 0;
}