NOIP2023模拟13联测34 origen

联测34 origen"/>

NOIP2023模拟13联测34 origen

题目大意

给定 n n n个整数 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1​,a2​,…,an​，求

∑ i = 1 n ∑ j = i n ( ⨁ k = i j a k ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n(\bigoplus\limits _{k=i}^ja_k)^2 i=1∑n​j=i∑n​(k=i⨁j​ak​)2

输出答案模 998244353 998244353 998244353后的值。

注： ⨁ k = i j a k = a i ⊕ a i + 1 ⊕ ⋯ ⊕ a j \bigoplus\limits _{k=i}^ja_k=a_i\oplus a_{i+1}\oplus \cdots \oplus a_j k=i⨁j​ak​=ai​⊕ai+1​⊕⋯⊕aj​

1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ a i ≤ 2 × 1 0 5 1\leq n\leq 2\times 10^5,1\leq a_i\leq 2\times 10^5 1≤n≤2×105,1≤ai​≤2×105

题解

令 d i = ⨁ j = 1 i a j d_i=\bigoplus\limits _{j=1}^ia_j di​=j=1⨁i​aj​，则原式变为

∑ i = 1 n ∑ j = i n ( d j ⊕ d i − 1 ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n(d_j\oplus d_{i-1})^2 i=1∑n​j=i∑n​(dj​⊕di−1​)2

我们按位来考虑，枚举每一位 k k k，那么原式变为

∑ k = 0 m x 2 k ∑ ( d j ⊕ d i − 1 ) & 2 k = 2 k ( d j ⊕ d i − 1 ) \sum\limits_{k=0}^{mx}2^k\sum\limits_{(d_j\oplus d_{i-1})\& 2^k=2^k}(d_j\oplus d_{i-1}) k=0∑mx​2k(dj​⊕di−1​)&2k=2k∑​(dj​⊕di−1​)

其中 m x mx mx表示所有 d i d_i di​的二进制最高位的是从低到高的第几位。

我们可以用 v e c t o r vector vector来存每一位为 0 0 0或为 1 1 1的数。也就是说，对于每个数 d i d_i di​，枚举它的每一位 k k k，如果这一位为 0 0 0，则将 d i d_i di​放在 v k , 0 v_{k,0} vk,0​中；如果这一位为 1 1 1，则将 d i d_i di​放在 v k , 1 v_{k,1} vk,1​中。这里的 v k , 0 / 1 v_{k,0/1} vk,0/1​是 v e c t o r vector vector类型的。

然后，枚举每一个 k k k，我们要求的就是 ∑ ( d j ⊕ d i − 1 ) & 2 k = 2 k ( d j ⊕ d i − 1 ) \sum\limits_{(d_j\oplus d_{i-1})\& 2^k=2^k}(d_j\oplus d_{i-1}) (dj​⊕di−1​)&2k=2k∑​(dj​⊕di−1​)。既然要异或后的第 k k k位为 1 1 1，那么 d j d_j dj​和 d i − 1 d_{i-1} di−1​的第 k k k位肯定不同。那么，我们需要求 v k , 0 v_{k,0} vk,0​和 v k , 1 v_{k,1} vk,1​中各取一个数来异或，然后将所有情况求和。

这怎么处理呢？我们还是按每一位来计算。枚举每一位 t t t，如果异或和的第 t t t位为 1 1 1，则在 v k , 0 v_{k,0} vk,0​中选的数和 v k , 1 v_{k,1} vk,1​中选的数的第 t t t位肯定不同。那么，我们记录 v k , 0 v_{k,0} vk,0​中的每一位 t t t有多少个数为 0 0 0，多少个数为 1 1 1，记为 h v t , 0 / 1 hv_{t,0/1} hvt,0/1​，那么对于 v k , 1 v_{k,1} vk,1​中的每一位 t t t，设这一位为 v v v（ v v v的值为 0 0 0或 1 1 1），其贡献为 2 t × h v t , 1 − v 2^t\times hv_{t,1-v} 2t×hvt,1−v​。

注意 d 0 d_0 d0​也要加入 v e c t o r vector vector。因为这是 v k , 0 v_{k,0} vk,0​中的数异或 v k , 1 v_{k,1} vk,1​中的数，所以是有序的，不需要除以 2 2 2。

时间复杂度为 O ( n log ⁡ 2 n ) O(n\log^2 n) O(nlog2n)。

code

#include<bits/stdc++.h>
using namespace std;
const int N=200000;
const long long mod=998244353;
int n,a[N+5],b[N+5],hv[25][2];
long long ans=0;
vector<int>v[25][2];
int main()
{
//	freopen("origen.in","r",stdin);
//	freopen("origen.out","w",stdout);scanf("%d",&n);for(int j=0;j<=19;j++){v[j][0].push_back(0);}for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=b[i-1]^a[i];for(int j=0;j<=19;j++){v[j][(b[i]>>j)&1].push_back(b[i]);}}for(int i=0;i<=19;i++){for(int j=0;j<=19;j++) hv[j][0]=hv[j][1]=0;for(int j=0;j<v[i][0].size();j++){int t=v[i][0][j];for(int k=0;k<=19;k++){++hv[k][(t>>k)&1];}}long long tmp=0;for(int j=0;j<v[i][1].size();j++){int t=v[i][1][j];for(int k=0;k<=19;k++){int vk=((t>>k)&1)^1;tmp=(tmp+1ll*hv[k][vk]*(1<<k))%mod;}}ans=(ans+tmp*(1<<i))%mod;}printf("%lld",ans);return 0;
}