题目描述

难度分:$1700$

输入$n(1 \leq n \leq 3 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$。

定义$f(L,R)$为连续子数组$a[L]$到$a[R]$的异或和。

计算所有$f(L,R) \times (R-L+1)$的和，其中$L \leq R$。

输出答案模$998244353$的结果。

输入样例$1$

3
1 3 2

输出样例$1$

12

输入样例$2$

4
39 68 31 80

输出样例$2$

1337

输入样例$3$

7
313539461 779847196 221612534 488613315 633203958 394620685 761188160

输出样例$3$

257421502

算法

按位贡献

由于$n \leq 3 \times 10^5$，肯定不能枚举所有的子数组，统计所有子数组的贡献，因为子数组的数量就有$O(n^2)$的级别。

先考虑一个比较暴力的做法，枚举子数组的右端点$r \in [1,n]$，此时对于一个合法的子数组$[l,r]$，它对答案的贡献就应该是$s=\Sigma_{l \in [1,r]}f(l,r) \times (r-l+1)$。如果预处理出一个前缀和数组$eor$，$eor[i]=\oplus_{k=1}^{i}a[i]$，则$f(l,r)=eor[r] \oplus eor[l-1]$，$s$就可以化简为

$s=\Sigma_{l \in [1,r]}eor[r] \oplus eor[l-1] \times (r-l+1)$
$=\Sigma_{l \in [0,r)}eor[r] \oplus eor[l] \times (r-l)$。
$=r \times \Sigma_{l \in [0,r)}eor[r] \oplus eor[l] - \Sigma_{l \in [0,r)}eor[r] \oplus eor[l] \times l$

此时我们希望当遍历到$r$时，可以把所有以$a[r]$结尾的子数组贡献都在常数时间$O(1)$下计算出来。所以我们希望知道有多少个$eor[l]$和$eor[r]$异或之后可以不为$0$，但是如果不拆位，$eor[i]$的值域就会非常庞大，无法计算，因此我们需要按位预处理出每一个位$b$的前缀异或和数组，根据题面所给的$a[i]$范围，可以开$31$位（$0$~$30$）。此时对于某一位$b$，有贡献值

$s_b=2^b \times r \times \Sigma_{l \in [0,r)}eor[b][r] \oplus eor[b][l] - 2^b \times \Sigma_{l \in [0,r)}eor[b][r] \oplus eor[b][l] \times l$

当遍历$r \in [1,n]$时，维护$l \in [0,r)$中，前缀异或$eor[b][l]$为$0$或$1$时的频数，记录在$cnt$数组中，索引之和记录在$sum$数组中，这样$s_b$就可以化为

$s_b=2^b \times (r \times cnt[1-eor[b][r]] - sum[1-eor[b][r]])$

如此一来，就可以$O(1)$计算出每个$r \in [1,n]$在各个二进制位上的贡献了。外层循环遍历位$b \in [0,30]$，内层循环枚举子数组的右端点$r \in [1,n]$，计算该位的贡献。

复杂度分析

时间复杂度

预处理出每一位$b$的前缀异或和数组，时间复杂度为$O(30n)$。接下来按位统计每个$r \in [1,n]$的贡献，统计每一位的贡献时间复杂度也是线性的，因此时间复杂度还是$O(30n)$。整个算法的时间复杂度为$O(n)$，可以看成有个比较大的常数$A$，其中$A=log_2(max_{i \in [1,n]}a[i])$。

空间复杂度

空间消耗的瓶颈主要就在于每一位的前缀异或数组$eor$，每一位的空间都是$O(n)$的，由于实现时是全局变量，根据题目的数据范围一共有$30$位。而理论上整个算法的额外空间复杂度为$O(n)$，也可以看成有个比较大的常数$A$，其中$A=log_2(max_{i \in [1,n]}a[i])$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 300010, MOD = 998244353;
int n, a[N];
LL eor[31][N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int b = 0; b <= 30; b++) {
        for(int i = 1; i <= n; i++) {
            eor[b][i] = eor[b][i - 1] ^ (a[i]>>b&1);
        }
    }
    LL ans = 0;
    for(int b = 0; b <= 30; b++) {
        LL cnt[2] = {0}, sum[2] = {0};
        cnt[0] = 1;
        for(int r = 1; r <= n; r++) {
            LL bv = eor[b][r];
            if(cnt[1 - bv] > 0) {
                ans = (ans + r*cnt[1 - bv]%MOD*(1ll<<b)%MOD) % MOD;
                ans = (ans - sum[1 - bv]*(1ll<<b)%MOD + MOD) % MOD;
            }
            cnt[bv]++;
            sum[bv] = (sum[bv] + r) % MOD;
        }
    }
    printf("%lld\n", ans);
    return 0;
}