20230818比赛题解

wflengxuenong · 2023-08-26 17:25:24 · 个人记录

T4

100pts:

按二进制位枚举，对于第j位：

设\sum _{l_1 \le r_1 \le i} XOR(l_1,r_1)的值为f1[i][j] 。如果第j位为0，f1[i][j] = f1[i-1][j] + sum1[i][j] \times 2^j，如果第j位为1，f1[i][j] = f1[i-1][j] + sum0[i][j] \times 2^j ，其中sum0/1[i][j]= \sum _{l \le i} XOR(l,i)，只考虑第j位。

然后把f1的每一位综合起来，得到f1[i]= \sum f1[i][j]

设\sum _{l_1 \le r_1 < l_2 \le r_2 \le i} XOR(l_1,r_1) \times XOR(l_2,r_2)的值为f2[i][j] 。如果第j位为0，f2[i][j] = f2[i-1][j] + sum1[i][j] \times 2^j，如果第j位为1，f2[i][j] = f2[i-1][j] + sum0[i][j] \times 2^j ，其中sum0/1[i][j]= \sum _{l \le i} f1[l-1] \times XOR(l,i)，只考虑第j位。

然后把f2的每一位综合起来，得到f2[i]= \sum f2[i][j]

设\sum _{l_1 \le r_1 < l_2 \le r_2 < l_3 \le r_3 \le i} XOR(l_1,r_1) \times XOR(l_2,r_2) \times XOR(l_2,r_2)的值为f3[i][j] 。如果第j位为0，f3[i][j] = f3[i-1][j] + sum1[i][j] \times 2^j，如果第j位为1，f3[i][j] = f3[i-1][j] + sum0[i][j] \times 2^j ，其中sum0/1[i][j]= \sum _{l \le i} f2[l-1] \times XOR(l,i)，只考虑第j位。

然后把f3的每一位综合起来，得到f3[i]= \sum f3[i][j]，即为答案

另一种统计答案的方式是正着求f2，倒着求f1，然后枚举r_2的位置。

70pts:

设\sum _{l_1 \le r_1 \le i} XOR(l_1,r_1)的值为f1[i] 。