疑惑亦或异或 - 动态规划解题详解

题目背景

这道题是一道算法题，需要求解一个数学公式的值。题目背景是有一个入魔的OIer，他因为深夜做题走火入魔，设计了这道题目来解救他自己。

题目描述

给定一个长度为n的数组a，求出下式在模998244353意义下的答案。

$$\sum _{1\le l_1\le r_1 < l_2\le r_2 < l_3\le r_3 \le n} XOR(l_1,r_1) \times XOR(l_2,r_2) \times XOR(l_3,r_3)$$

其中，XOR(l,r) = a_l ⊕ a_{l+1} ⊕ ... ⊕ a_r

输入格式

第一行一个正整数表示数组a的长度n。

第二行n个非负整数，第i个整数表示a_i。

输出格式

一个整数，表示和式在模998244353意义下的值。

样例 #1

样例输入 #1

3
1 2 3

样例输出 #1

样例 #2

样例输入 #2

4
1 1 1 0

样例输出 #2

提示

数据范围

对于10%的数据，n ≤ 10。
对于30%的数据，n ≤ 100。
对于70%的数据，n ≤ 5000。
对于另外10%的数据，0 ≤ a_i ≤ 1。
对于100%的数据，3 ≤ n ≤ 200000, 0 ≤ a_i ≤ 10^9。

解题思路

这道题可以使用动态规划的方法来解决。

首先，我们需要定义一个二维数组dp，dp[i][j]表示前j个数中有i个数的异或和。

然后，我们需要定义一个二维数组preV，preV[c][0]和preV[c][1]分别表示前j个数中，二进制位c为0或1的个数。

接下来，我们开始进行动态规划。

首先，初始化dp[0][j]为1，表示前j个数中有0个数的异或和为1。

然后，我们需要计算dp[k][j]，其中k表示前j个数中有k个数的异或和。

我们遍历数组a，对于第j个数a[j]，我们计算前j个数中a[j]的二进制位c为0或1时，dp[k][j]的值。

具体计算方法如下：

我们用变量pre表示前j个数的异或和，初始化为0。
我们遍历二进制位c的范围，对于每个c，我们计算preV[c][0]和preV[c][1]，分别表示前j个数中二进制位c为0或1的个数。
我们用变量cur表示当前dp[k][j]的值，初始化为0。
我们遍历二进制位c的范围，对于每个c，我们计算cur的值。具体计算方法为cur += preV[c][(pre >> c & 1) ^ 1] * two_pow[c]，其中pre >> c & 1表示pre的二进制位c的值，(pre >> c & 1) ^ 1表示pre的二进制位c取反的值，two_pow[c]表示2的c次方。
我们更新dp[k][j]的值为dp[k][j-1] + cur，并取模998244353。
我们更新preV数组的值，具体更新方法为preV[c][pre >> c & 1] += dp[k-1][j]，并取模998244353。

最后，我们输出dp[3][n]的值，即为所求的答案。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A[200001];
ll dp[4][200001];
ll two_pow[30];
ll preV[30][2];
int mod=998244353;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int idx = 0; idx <= n; idx++) dp[0][idx] = 1;
    for (int i = 0; i < 30; i++) two_pow[i] = ((ll)pow(2,i))%mod;
    for (int k = 1; k <= 3; k++) {
        int pre = 0;
        memset(preV,0,sizeof(preV));
        for (int c = 0; c < 30; c++) 
		preV[c][0] += dp[k - 1][0];
        for (int idx = 1; idx <= n; idx++) {
            pre ^= A[idx];
            ll cur = 0;
            for (int c = 0; c < 30; c++) 
			cur += preV[c][(pre >> c & 1) ^ 1] * two_pow[c],cur%=mod;
            dp[k][idx] = dp[k][idx - 1] + cur;
            dp[k][idx]%=mod;
            for (int c = 0; c < 30; c++) 
			preV[c][pre >> c & 1] += dp[k - 1][idx],preV[c][pre >> c & 1]%=mod;
        }
    }
    cout << dp[3][n];
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n