解法：模拟

每次操作会让数组的总和减一，因此答案就是总和 $\mod k$ 的值。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int sm = 0;
        for (int x : nums) sm += x;
        return sm % k;
    }
};

解法：前缀和

假设先不考虑长度被 $k$ 整除，直接求最大和非空子数组，有一种使用前缀和的解法：枚举子数组的右端点，那么最佳左端点就是之前出现过的前缀和最小的位置。

加入长度被 $k$ 整除的条件，思路也是一样的，只不过额外限制了左右端点的下标 $\bmod k$ 的值需要相同。因此将下标按 $\bmod k$ 分类，用一个数组记录每类下标出现过的最小前缀和即可。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###cpp

class Solution {
public:
    long long maxSubarraySum(vector<int>& nums, int K) {
        int n = nums.size();

        const long long INF = 1e18;
        // mn[x] 表示 mod k = x 的下标出现过的最小前缀和
        long long mn[K];
        for (int i = 0; i < K; i++) mn[i] = INF;
        mn[K - 1] = 0;

        long long ans = -INF, sm = 0;
        // 枚举子数组右端点
        for (int i = 0; i < n; i++) {
            sm += nums[i];
            ans = max(ans, sm - mn[i % K]);
            mn[i % K] = min(mn[i % K], sm);
        }
        return ans;
    }
};

解法：DP

维护 f[i][j][t] 表示以 (i, j) 为终点，且路径和 mod k 等于 t 的路径数。答案就是 f[n - 1][m - 1][0]。

转移方程为：

f[i][j][t] =
    f[i - 1][j][(t - grid[i][j]) mod k] + // 从上方走过来
    f[i][j - 1][(t - grid[i][j]) mod k]   // 从左方走过来

复杂度 $\mathcal{O}(nmk)$。

参考代码（c++）

###c++

class Solution {
    int n, m;
    const int MOD = 1000000007;

public:
    int numberOfPaths(vector<vector<int>>& grid, int K) {
        n = grid.size(); m = grid[0].size();

        long long f[n][m][K];
        memset(f, 0, sizeof(f));
        // 初值
        f[0][0][grid[0][0] % K] = 1;

        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < K; k++) {
            // 从上方走过来
            if (i > 0) f[i][j][k] = (f[i][j][k] + f[i - 1][j][(k - grid[i][j] % K + K) % K]) % MOD;
            // 从左方走过来
            if (j > 0) f[i][j][k] = (f[i][j][k] + f[i][j  - 1][(k - grid[i][j] % K + K) % K]) % MOD;
        }
        return f[n - 1][m - 1][0];
    }
};