題意

傳送門 LeeCode 1787 使所有區間的異或結果為零

題解

任一個元素都至多對$k$個長度為$k$的區間產生影響，故難以直接依次處理每一個元素。

觀察到滿足條件的數組中模$k$意義下索引相等的各個元素相同，故可以依次處理每一個同余類。$dp[i][j]$表示前$i$個同余類異或結果為$j$情況下的最小更改元素數。直接枚舉每一種取值，時間復雜度$O(n{2}^{20})$，難以勝任。設同余類$i$元素規模為$m$，則至多改動$m$個元素，則可以從任一個狀態轉移過來，那么貪心地選擇改動數量最少的狀態即可。對于出現在同余類中的取值，直接暴力枚舉即可。總時間復雜度$O(n{2}^{10})$。

#include <bits/stdc++.h>
using namespace std;class Solution {public:int minChanges(vector<int>& nums, int k) {vector<map<int, int>> cnt(k);vector<int> num(k);int n = nums.size();for (int i = 0; i < n; ++i) {num[i % k] += 1;cnt[i % k][nums[i]] += 1;}auto _min = [](int& x, int y) {x = min(x, y);};const int lg = 10;const int inf = 1e9;vector<vector<int>> dp(k + 1, vector<int>(1 << lg, inf));dp[0][0] = 0;for (int i = 0; i < k; ++i) {int m = num[i];int p = min_element(dp[i].begin(), dp[i].end()) - dp[i].begin();for (int j = 0; j < 1 << lg; ++j) {for (auto& [x, c] : cnt[i]) {_min(dp[i + 1][j], dp[i][j ^ x] + m - c);}_min(dp[i + 1][j], dp[i][p] + m);}}return dp[k][0];}
};