---
tags: 题解, 算法
title: 从入门到头秃周末休闲赛67
---

# XOR划分

对于所有数的XOR结果不为0的情况，那就简单了，设其为m，那么每一段的XOR结果一定为m，且一定分为奇数段。我们再对原始数组求前缀异或，设新数组为 $s$ ，元素为 $s_i$ ，那么我们就只需要关注 $s_i=0$ 或 $s_i=m$ 时的 $i$ 值，我们把这些值提取到数组 $t_i$ ，且非0均取为1，再定义`dp[i][j]`表示到第i个元素且以j为末尾时的分割数量，那么可以得到DP的递推方程

dp[0][0] = 1
dp[0][1] = 0
dp[i][ti] = dp[i-1][ti] + dp[i-1][!ti]
dp[i][!ti] = dp[i-1][!ti]

但是对于所有数的XOR结果为0时，那每一段的异或结果就变成未知了，于是，我们就穷举m的值，没错，就是把 $s_i$ 中每个值都设为m来分别计算。但是，这样暴力来必然超时。我们改为对 $s_i$ 按相同值分组。同时，我们要把上面的dp方程改改，提取到数组 $u_i$ ，其元素表示距离下一个非0元素之间有多少个0，类似游程长度编码，例如数组

`1 0 0 1 1 0 0 0 1 0`

转换为

`2 0 3 1`

这样，DP的时间复杂度是 $O(n)$ ，且n是非0数的数量，且由于不同的非0值并不会重复计算，所以整体复杂度仍然是 $O(n)$ 。