NOIP2023模拟13联测34 A. origenNOIP2023模拟13联测34 A. origen

联测34 A. origenNOIP2023模拟13联测34 A. origen"/>

NOIP2023模拟13联测34 A. origenNOIP2023模拟13联测34 A. origen

NOIP2023模拟13联测34 A. origen

文章目录

• NOIP2023模拟13联测34 A. origen
• • 题目大意
  • 思路
  • code

题目大意

给定 n n n 个整数 a 1 , a 2 , a 3 ⋯ a n a_1,a_2,a_3\cdots a_n a1​,a2​,a3​⋯an​ ，求
∑ i = 1 n ∑ j = i n ( ⊕ k = i j a k ) 2 m o d 998244353 \sum_{i = 1}^n\sum_{j = i}^n(\oplus_{k = i}^ja_k)^2 \mod 998244353 i=1∑n​j=i∑n​(⊕k=ij​ak​)2mod998244353
n ≤ 2 ∗ 1 0 5 , 0 ≤ a i ≤ 2 ∗ 1 0 5 n\le 2 * 10^5 , 0\le a_i \le 2 * 10 ^5 n≤2∗105,0≤ai​≤2∗105

思路

设 s i = ⊕ j = 1 i a j s_i = \oplus_{j = 1}^i a_j si​=⊕j=1i​aj​ ，则原式变为：
∑ i = 0 n − 1 ∑ j = 1 n ( s i ⊕ s j ) 2 \sum_{i = 0}^{n - 1} \sum_{j = 1}^n (s_i \oplus s_j)^2 i=0∑n−1​j=1∑n​(si​⊕sj​)2
按位考虑，一个数可以用二次幂的和来表示。考虑怎么处理平方。

因为:
( ∑ i = 1 n a i ) 2 = ∑ i = 1 i a i 2 + 2 ∑ i = 1 n − 1 ∑ j = i + 1 n a i ∗ a j (\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=1∑n​ai​)2=i=1∑i​ai2​+2i=1∑n−1​j=i+1∑n​ai​∗aj​
把两部分分开处理。

先处理前面的那项

把 i i i 的每一位分开求贡献，当前处理到第 j j j 位

设前 i − 1 i - 1 i−1 个数这一位为 0 0 0 的数有 s 0 s0 s0 个，为 1 1 1 的数有 s 1 s1 s1 个

那么求这一位的贡献

• 若当前这一位为 1 1 1 ： 2 j ∗ 2 ∗ s 0 2^j*2*s0 2j∗2∗s0
• 若当前这一位为 0 0 0 ： 2 j ∗ 2 ∗ s 1 2^j*2*s1 2j∗2∗s1

然后处理后面的那项

先枚举两位 j 1 , j 2 j1 , j2 j1,j2

当前处理到第 i i i 位

设 s u m k , l sum_{k , l} sumk,l​ 为前面 i − 1 i - 1 i−1 个数的第 j 1 j1 j1 位为 k k k ，第 j 2 j2 j2 位为 l l l 的个数

设第 i i i 个数这两位分别是 x , y x , y x,y

那么这里的贡献为： 2 ∗ 2 j 1 ∗ 2 j 2 ∗ s u m ! x , ! y 2 *2^{j1} * 2^{j2} *sum_{!x , !y} 2∗2j1∗2j2∗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;
}