题意：
给你一个整数数组 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
思路：
动态规划
设数组nums的长度为n，首先我们需要分析出数组nums在修改之后应当具有哪些性质。
由于任意长度为k的区间异或结果等于0，那么对于任意的i，有：
nums[i]⊕nums[i+1]⊕⋯⊕nums[i+k−1]=0 (1)
以及：
nums[i+1]⊕nums[i+2]⊕⋯⊕nums[i+k]=0 (2)
其中⊕表示异或运算。根据异或运算的性质 a⊕b⊕b=a，将(1)(2)两式联立，即可得到：
nums[i]⊕nums[i+k]=0
其等价于nums[i]=nums[i+k]。因此我们可以得出一个重要的结论：
数组 nums 在修改之后是一个以 k 为周期的周期性数组，即 ∀i∈[0,n−k),nums[i]=nums[i+k]。
因此，我们可以将数组nums按照下标对k取模的结果0,1,⋯,k−1 分成 k 个组，每个组内的元素必须要相等，并且这 k 个组对应的元素的异或和为 0，即：
nums[0]⊕nums[1]⊕⋯⊕nums[k−1]=0
只要满足上述的要求，修改后的数组的所有长度为 k 的区间异或结果一定等于 0。
对于第i个组，我们可以使用哈希映射来存储该组内的元素以及每个元素出现的次数，这样一来，我们就可以尝试使用动态规划来解决本题了。
设 f(i,mask) 表示我们已经处理了第0,1,⋯,i 个组，并且这些组对应元素的异或和：
nums[0]⊕nums[1]⊕⋯⊕nums[i]
为 mask 的前提下，这些组总计最少需要修改的元素个数。在进行状态转移时，我们可以枚举第 i 组被修改成了哪个数。假设其被修改成了 x，那么第 0,1,⋯,i−1 个组对应的元素的异或和即为 mask⊕x，因此我们可以得到状态转移方程：
f(i,mask)= min{f(i−1,mask⊕x)+size(i)−count(i,x)}
其中 size(i) 表示第 i 个组里的元素个数，count(i,x) 表示第 i 个组里元素 x 的次数，它们的值都可以通过哈希映射得到。上述状态转移方程的意义即为：如果我们选择将第 i 组全部修改为 x，那么有 count(i,x) 个数是无需修改的，这样就需要修改 size(i)−count(i,x) 次。
优化
对于未优化的状态转移方程：
f(i,mask)= min{f(i−1,mask⊕x)+size(i)−count(i,x)}
首先 size(i) 是与 x 无关的常量，我们可以将其移出最小值的限制，即：
f(i,mask)=size(i)+ min{f(i−1,mask⊕x)−count(i,x)}
由于我们需要求的是「最小值」，因此在状态转移方程中添加若干大于等于「最小值」的项，对最终的答案不会产生影响。
考虑 count(i,x) 这一项，如果 xx 没有在哈希表中出现，那么这一项的值为 0，否则这一项的值大于 0。即：
如果 x 没有在哈希表中出现，那么转移的状态为：
f(i−1,mask⊕x)
如果 x 在哈希表中出现，那么转移的状态为：
f(i−1,mask⊕x)−count(i,x)
它严格小于 f(i−1,mask⊕x)。如果我们在状态转移方程中添加 f(i−1,mask⊕x)，最终的答案不会变化。
因此我们可以将状态转移方程变化为：
f(i,mask)=size(i)+min{t1,t2}
其中 t1对应 x 在哈希表中出现的状态，即：
t1=min{f(i−1,mask⊕x)−count(i,x)}
t2对应 x 不在哈希表中出现的状态，以及 x 在哈希表中出现并且我们额外添加的状态，即：
t2=minf(i−1,mask⊕x)
class Solution {
private:
// x 的范围为 [0, 2^10)
static constexpr int MAXX = 1 << 10;
// 极大值，为了防止整数溢出选择 INT_MAX / 2
static constexpr int INFTY = INT_MAX / 2;
public:
int minChanges(vector<int>& nums, int k) {
int n = nums.size();
vector<int> f(MAXX, INFTY);
// 边界条件 f(-1,0)=0
f[0] = 0;
for (int i = 0; i < k; ++i) {
// 第 i 个组的哈希映射
unordered_map<int, int> cnt;
int size = 0;
for (int j = i; j < n; j += k) {
++cnt[nums[j]];
++size;
}
// 求出 t2
int t2min = *min_element(f.begin(), f.end());
vector<int> g(MAXX, t2min);
for (int mask = 0; mask < MAXX; ++mask) {
// t1 则需要枚举 x 才能求出
for (auto [x, countx]: cnt) {
g[mask] = min(g[mask], f[mask ^ x] - countx);
}
}
// 别忘了加上 size
for_each(g.begin(), g.end(), [&](int& val) {val += size;});
f = move(g);
}
return f[0];
}
};
