题目描述
给定一个长为 $n$ 的自然数数列 $a$ 和一个正整数 $k$，问最少修改 $a$ 中的多少个整数（修改后必须也为整数）能使整个序列的所有长为 $k$ 的区间的元素和都为偶数。
数据范围：$1\le k\le n\le 10^6$，$0\le a_i\le 10^9$。
分析
首先，因为我们只关心结果的奇偶，所以我们可以直接将数列转为 $0/1$ 序列（所有数对 $2$ 取模），并将求和改为求异或和。
然后，我们注意到，这个数列中 $[i,i+k-1]$ 这个区间内元素的异或和与 $[i+1,i+k]$ 这个区间内元素的异或和相等（都为 $0$）。将两式异或，得到 $a_i\oplus a_{i+k}=0$，即 $a_i=a_{i+k}$。所以我们得到一个重要结论：修改后的序列中，下标模 $k$ 相等的位置上的数，奇偶性一定相同。
因此，我们可以计算序列中下标模 $k$ 相等的数中有多少个 $0$（偶数）和多少个 $1$（奇数）。设下标取模后的结果为 $r$（我的代码中 $r$ 取 $1$ 到 $k$），则 $cnt_{r,0}$ 表示这些数中偶数的个数，$cnt_{r,1}$ 类似（奇数的个数）。
这样，我们就将问题转化为了下面这样：
有一个长为 $k$ 的数列，第 $i$ 个位置上填 $0$ 会有 $cnt_{i,\color{red}1}$ 的代价，填 $1$ 会有 $cnt_{i,\color{red}0}$ 的代价（注意下标，是要改成目标数的数的个数，而非目标数的个数），且只能填 $0$ 或 $1$ 中的一个，不能不填。要求所有位上的数的异或和为 $0$，求最小总代价。
显然，我们可以 DP 解决。
设 $dp_{i,0}$ 表示第 $i$ 位填 $0$ 在以 $i$ 结尾的前缀中的最小总代价（$dp_{i,1}$ 类似，表示第 $i$ 位填 $1$），则根据异或运算的定义，我们可以很容易地得出：
$$dp_{i,0}=\max(dp_{i-1,0}+cnt_{i,1},dp_{i-1,1}+cnt_{i,0})$$
$$dp_{i,1}=\max(dp_{i-1,1}+cnt_{i,1},dp_{i-1,0}+cnt_{i,0})$$
特别地，当 $i=1$ 时，$dp_{1,0}=cnt_{1,1}$，$dp_{1,1}=cnt_{1,0}$。（如果你忘记了这条然后交了一发，你就会被 Test #1 给 hack 掉）
最后我们输出 $dp_{k,0}$ 就结束了。（如果下标采用 $0$ 到 $k-1$，请注意你的 DP 起终点和输出内容）
输入+处理 $cnt$ 数组的时间复杂度为 $\mathcal{O}(n)$，DP 的复杂度也为 $\mathcal{O}(n)$，所以完全没有问题！
代码的具体实现在上文中讲得很清楚，因此不展示。
感谢您的阅读！