当前位置：首页 > news >正文

Educational Codeforces Round 155 (Rated for Div. 2) - D Sum of XOR Functions

news 2025/9/2 5:32:54

学到的几个知识点：

1.拆位

对于整体上的异或操作可以转化为31个二进制位上的操作，每一位再×上 $2^{i}$ 。

将一次操作拆为31次来方便操作。

s[i]表示异或前缀和，l~r间的异或和为s[r] ^ s[l - 1] ---->

拆完位后这个公式还能再推出一个性质：

只有s[r] != s[l - 1]时这段区间的异或和才为1，来以右端点为1还是0来讨论一下：

对于每一位1，只有左端点的左边一位为0时才有值，才可以计算进去

对于每一位0，只有左端点的左边一位为1时才有值，才可以计算进去

$\sum_{l = 1}^{n}\sum_{r = l}^{n}\sum_{i = 0}^{30}2^{i} * ((s[r] \&1) \wedge (s[l - 1] \& 1)) * (r - (l - 1))$

对于一位上的1，设当前为r,左边的为0的点为l,那要承的数就是(r - l),

如果这样的l有k个，就是k * r - ( $l_{1} + l_{2}+l_{3}+...+l_{k}$ )

这样就算出来了对于每一个数的每一位的贡献时间复杂度 O(31 * n)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;const int N = 300010, mod = 998244353;int n;
int a[N];
ll f[40][2], cnt[40][2];int main()
{IOScin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];a[i] ^= a[i - 1];//cout << a[i] << ' ';}//cout << endl;ll ans = 0;for(int i = 0; i <= n; i ++){for(int j = 0; j <= 30; j ++){if(a[i] >> j & 1){ans += (1ll << j) % mod * (((cnt[j][0] * i - f[j][0]) % mod + mod) % mod);ans %= mod;f[j][1] = (f[j][1] + i) % mod;cnt[j][1] ++;}else{ans += (1ll << j) % mod * (((cnt[j][1] * i - f[j][1]) % mod + mod) % mod);ans %= mod;f[j][0] = (f[j][0] + i) % mod;cnt[j][0] ++;}}}cout << ans;return 0;
}

查看全文

http://www.lryc.cn/news/176363.html