# 1787. 使所有区间的异或结果为零 ### 题目地址(1787. 使所有区间的异或结果为零) ### 题目描述 ``` 给你一个整数数组 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$？不清楚的可以看下这里 上面枚举 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 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://p.ipic.vip/mv7oxw.jpg) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1787.make-the-xor-of-all-segments-equal-to-zero.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.