# 1787. 使所有区间的异或结果为零

### 题目地址(1787. 使所有区间的异或结果为零)

<https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/>

### 题目描述

```
给你一个整数数组 nums​​​ 和一个整数 k​​​​​ 。区间 [left, right]（left <= right）的 异或结果 是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。

返回数组中 要更改的最小元素数 ，以使所有长度为 k 的区间异或结果等于零。

 

示例 1：

输入：nums = [1,2,0,3,0], k = 1
输出：3
解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]


示例 2：

输入：nums = [3,4,5,2,1,7,3,4,7], k = 3
输出：3
解释：将数组 [3,4,5,2,1,7,3,4,7] 修改为 [3,4,7,3,4,7,3,4,7]


示例 3：

输入：nums = [1,2,4,1,2,5,1,2,6], k = 3
输出：3
解释：将数组[1,2,4,1,2,5,1,2,6] 修改为 [1,2,3,1,2,3,1,2,3]

 

提示：

1 <= k <= nums.length <= 2000
​​​​​​0 <= nums[i] < 210
```

### 前置知识

* 异或
* 动态规划

### 公司

* 暂无

### 常规 DP

#### 思路

题目提到了：

```
区间 [left, right] 的异或和为 nums[left] XOR nums[left+1] XOR ... XOR nums[right]
```

你可以转化任意位置上的数字到任意值，求所有长度为 k 个的子数组异或和都为 0 的最小的改变次数。

不难知道两点:

1. 解的上限是 n，其中 n 为数组长度。
2. 转化后的 nums 数组满足 nums\[i] == nums\[i+k]，其中 0 <= i < n - k。这是由于异或的自反性决定的。

于是我们可以定义状态 dp\[i]\[j] 为处理到数组第 i 项， 且异或和为 j 的最小操作次数。之后可以通过动态规划来求解。

接下来，我们考虑 dp\[i]\[j] 如何由之前的状态转过来。

由于我们可以选择将 nums\[i] 修改为值 val（val 为符合题目限制条件的任意值），使得异或和为 j，那么修改前的异或值就是 val ^ j (仍然是异或的自反性)。最后只需要考虑将 nums\[i] 修改为 val 的操作数（代价）即可。

推上面的第二条知识，将 nums\[i] 修改为 val 会同时影响索引满足 i % k 的所有值。比如你将 nums\[0] 改成了 val，那么相应需要将 nums\[k], nums\[2 \* k], nums\[3 \* k] 统统改为 val。 为了叙述方便，我们将 i % k 相同的称为一组，其编号为 i % k。 这样一来，代价就是 a - b。其中 a 为分组数，b 为分组上值为 val 的个数。说人话就是分组中需要被改变的值（本来就是 val 了就不用改了）。

令 val ^ j 为 p，那么有：

```
dp[i][j] = min(dp[i-1][p] + size[i] - a)，其中 p 为任意满足题目范围的值。
```

其中 size\_i 为 `n // k + int(n % k > i)`， a 则可以预处理出来，具体参考下方代码。

根据上面的公式。我们需要枚举所有的 i，j，p，三层循环就出来了。

#### 关键点

* 异或的自反性
* 对值域（upper） 做 dp，而不是数组索引。

#### 代码

* 语言支持：Python3

Python3 Code:

```python
class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        counter = collections.defaultdict(int)
        UPPER = 2 ** 10
        n = len(nums)
        for i, num in enumerate(nums):
            counter[(i % k, num)] += 1
        dp = [[n] * UPPER for _ in range(k)]

        for i in range(k):
            size_i = n // k + int(n % k > i)
            for j in range(UPPER):
                for p in range(UPPER):
                    if i == 0:
                        dp[i][j] = size_i - counter[(i, j)]
                    else:
                        dp[i][j] = min(
                            dp[i][j],
                            dp[i - 1][p] + size_i - counter[(i, p ^ j)],
                        )
        return dp[-1][0]

```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n \* (k+upper^2))$
* 空间复杂度：$O(k \* upper)$

注意到 dp\[i]\[j] 仅仅依赖 dp\[i-1]\[...] ，这提示我们使用滚动数组进行优化。**由于 p 可能大于 j，因此至少需要两个 dp 数组，而不是一个**。

* 语言支持：Python3

Python3 Code:

```py
        counter = collections.defaultdict(int)
        UPPER = 2 ** 10
        n = len(nums)
        for i, num in enumerate(nums):
            counter[(i % k, num)] += 1
        dp = [n] * UPPER

        for i in range(k):
            size_i = n // k + int(n % k > i)
            nxt_dp = [n] * UPPER
            for j in range(UPPER):
                for p in range(UPPER):
                    if i == 0:
                        nxt_dp[j] = size_i - counter[(i, j)]
                    else:
                        nxt_dp[j] = min(
                            nxt_dp[j],
                            dp[p] + size_i - counter[(i, p ^ j)],
                        )
            dp = nxt_dp
        return dp[0]
```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n \* (k+upper^2))$
* 空间复杂度：$O(upper)$

### 优化的 DP

#### 思路

上面的解法时间复杂度为 $O(n \* (k+upper^2))$。代入题目的数据范围大概是 $10 ^ 9$，远远大于 $10^7$，很可能会超时。因此必须优化。

> 为什么是 $10^7$？不清楚的可以看下这里 <https://lucifer.ren/blog/2020/12/21/shuati-silu3/>

上面枚举 p 的部分其实是可以优化掉的。核心点是：

* 异或的自反性
* 从改成新的数和改成已有的数角度考虑

对于数组每一位，其实我们都有两种选择：

* 将 nums\[j] 改为分组中没有的数
* 将 nums\[j] 改为分组中已有的数

**情况一：将 nums\[j] 改为分组中没有的数**

如果将 nums\[j] 改为分组中没有的数，那么答案就是 `min(dp) + size_i`，这是因为**我们可以任意选择 dp 中的一项,假设其值为 x，那么我们可以将分组上的数全部改为 x^j，这样就得到了异或和 j**。这样的操作代价就是 dp\[q] + size\_i，其中 0 <= q < upper 。由于我们求的是最小值，那自然就是 `min(dp) + size_i`。

#### 情况二： 将 nums\[j] 改为分组中已有的数

这种情况我们可以枚举分组中所有的值 val，并令 count 为 该分组下 val 的出现次数。那么有：

```py
for val, count in counter[i].items():  # 改成这一列已有的数
    nxt_dp[j ^ val] = min(nxt_dp[j ^ val], dp[j] + size_i - count)
```

#### 关键点

* 从改成新的数和改成已有的数角度考虑

#### 代码

* 语言支持：Python3

Python3 Code:

```python
class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        counter = collections.defaultdict(lambda: collections.defaultdict(int))
        UPPER = 2 ** 10
        n = len(nums)
        for i, num in enumerate(nums):
            counter[i % k][num] += 1
        dp = [n] * UPPER
        dp[0] = 0

        for i in range(k):
            size_i = n // k + int(n % k > i)
            nxt_dp = [min(dp) + size_i] * UPPER  # 改成新的数
            for j in range(UPPER):
                for val, count in counter[i].items():  # 改成这一列已有的数
                    nxt_dp[j ^ val] = min(nxt_dp[j ^ val], dp[j] + size_i - count)
            dp = nxt_dp
        return dp[0]


```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n \* (k+upper))$
* 空间复杂度：$O(upper)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/mv7oxw.jpg)