NOIP2023模拟13联测34 A. origen
目录题目大意
给定 \(n\) 个整数 \(a_1,a_2,a_3\cdots a_n\) ，求
\[\sum_{i = 1}^n\sum_{j = i}^n(\oplus_{k = i}^ja_k)^2 \mod 998244353 \]\(n\le 2 * 10^5 , 0\le a_i \le 2 * 10 ^5\)
思路
设 \(s_i = \oplus_{j = 1}^i a_j\) ，则原式变为：
\[\sum_{i = 0}^{n - 1} \sum_{j = 1}^n (s_i \oplus s_j)^2 \]按位考虑，一个数可以用二次幂的和来表示。考虑怎么处理平方。
因为:
\[(\sum_{i = 1}^n a_i)^2 = \sum_{i = 1}^i a_i^2+ 2\sum_{i = 1}^{n - 1}\sum_{j = i +1}^n a_i*a_j \]把两部分分开处理。
先处理前面的那项
把 \(i\) 的每一位分开求贡献，当前处理到第 \(j\) 位
设前 \(i - 1\) 个数这一位为 \(0\) 的数有 \(s0\) 个，为 \(1\) 的数有 \(s1\) 个
那么求这一位的贡献
- 若当前这一位为 \(1\) ：\(2^j*2*s0\)
- 若当前这一位为 \(0\) ：\(2^j*2*s1\)
然后处理后面的那项
先枚举两位 \(j1 , j2\)
当前处理到第 \(i\) 位
设 \(sum_{k , l}\) 为前面 \(i - 1\) 个数的第 \(j1\) 位为 \(k\) ，第 \(j2\) 位为 \(l\) 的个数
设第 \(i\) 个数这两位分别是 \(x , y\)
那么这里的贡献为：\(2 *2^{j1} * 2^{j2} *sum_{!x , !y}\)
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int mod = 998244353 , inf = 2e5;
int n , a[inf + 5] , s[inf + 5] , sum[2][2];
long long ans;
int main () {
freopen ("origen.in" , "r" , stdin);
freopen ("origen.out" , "w" , stdout);
scanf ("%d" , &n);
fu (i , 1 , n) scanf ("%d" , &a[i]) , s[i] = s[i - 1] ^ a[i];
for (int j = 1 , l = 1 ; l <= inf ; l <<= 1 , j ++) {
for (int i = 1 , s0 = 1 , s1 = 0 ; i <= n ; i ++) {
if ((1 << (j - 1)) & s[i])
ans = (ans + 1ll * l * l * s0 % mod) % mod , s1 ++;
else
ans = (ans + 1ll * l * l * s1 % mod) % mod , s0 ++;
}
}
bool x , y;
for (int j1 = 1 , l1 = 1 ; l1 <= inf ; l1 <<= 1 , j1 ++) {
for (int j2 = j1 + 1 , l2 = l1 << 1 ; l2 <= inf ; l2 <<= 1 , j2 ++) {
sum[0][0] = 1 , sum[0][1] = sum[1][0] = sum[1][1] = 0;
fu (i , 1 , n) {
x = s[i] & (1 << (j1 - 1)) , y = s[i] & (1 << (j2 - 1));
ans = (ans + 2ll * l1 * l2 * sum[!x][!y] % mod) % mod;
sum[x][y] ++;
}
}
}
printf ("%lld" , ans);
return 0;
}