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

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

这个dp有点难想

wnj大佬（喂你脚下有坑）视频题解
吴自华题解

关于复杂度
首先代码到计算新的，复杂度已经有
到计算已经有的，group[i]里存的数和外面的遍历k结合，实际上访问了N次，也可以理解为内外两层for刚好把N个数遍历完，因此这一部分复杂度是

总复杂度为两部分加和

class Solution {
public:
    int minChanges(vector<int> &nums, int k) {
        const int MAXV = 1024;
        const int INF = 0x3f3f3f3f;
        int n = nums.size();

        vector<int> size(k);  // 统计这一列总共多少数
        vector<unordered_map<int, int>> group(k + 1);  // 统计这一列每个数出现的次数

        for (int i = 0; i < n; i++) {
            group[i % k][nums[i]]++;
            size[i % k]++;
        }
        int dp[k + 1][MAXV];
        memset(dp, 0x3f, sizeof dp);
        dp[0][0] = 0;

        // dp[i][v]: 前i个数，异或和为v所要改的数最小值

        // 状态转移方程：
        // dp[i][v^s]=dp[i-1][v]+cost(s);
        // s是要改成的数
        // 当s是这一列全新的数的时候，cost(s)=size[i] (i是这一列)
        // 当s是这一列已经有的数的时候，cost(s)=size[i]-freq(s) (freq(s)是s在这一列出现的次数)
        for (int i = 1; i <= k; i++) {
            // 改成新的
            int mn = INF;
            for (int j = 0; j < MAXV; j++)mn = min(mn, dp[i - 1][j]);
            for (int j = 0; j < MAXV; j++)dp[i][j] = mn + size[i - 1];

            // 改成已存在的
            for (auto p:group[i - 1]) {
                for (int v = 0; v < MAXV; v++) {
                    int s = p.first, freq = p.second;
                    dp[i][s ^ v] = min(dp[i][s ^ v], dp[i - 1][v] + size[i - 1] - freq);
                }
            }
        }
        return dp[k][0];
    }
};