给定一个 N×MN×M 的矩阵 AA，请你统计有多少个子矩阵 (最小 1×11×1，最大 N×MN×M) 满足子矩阵中所有数的和不超过给定的整数 KK?

思路：前缀和+二分

首先计算矩阵的前缀和，然后枚举子矩阵的左上角和右下角，计算该子矩阵的和。

这个过程中可以使用二分查找来确定右下角的位置。具体地，假设当前枚举的左上角为 $(i,j)$，则右下角的行数必须不小于 $i$，列数必须不小于 $j$，否则子矩阵的大小会小于 $1\times1$。因此，我们可以枚举右下角的行号 $r$，然后使用二分查找确定最小的列号 $c$，使得子矩阵 $(i,j)\sim(r,c)$ 的和不超过 $K$。这个过程可以在 $O(\log M)$ 的时间内完成。

由于行和列都是独立的，因此我们可以分别计算行和列的前缀和，然后分别枚举行和列的位置，计算子矩阵的和。这样时间复杂度就降到了 $O(NM\log M)$。

时间复杂度：$O(NM\log M)$

参考代码：

相关问题

给定一个 N \times MN×M 的矩阵 AA，请你统计有多少个子矩阵 (最小 1 \times 11×1, 最大 N \times M)N×M) 满足子矩阵中所有数的和不超过给定的整数 KK。

这是一个经典的动态规划（Dynamic Programming）问题，通常可以通过使用二维数组来存储中间结果来解决。我们可以定义一个二维数组 dp[N+1][K+1]，其中 dp[i][j] 表示在一个大小为 i \times j i×j 的子矩阵中，元素之和最大为 j 时的情况数量。

算法步骤如下：

1. 初始化：dp[0][0] = 1，表示空矩阵（即没有元素）满足条件；对于其他元素，dp[i][0] 和 dp[0][j] 都设置为 0，因为至少有一个元素的和必须大于 0。

2. 计算过程：遍历矩阵 A 中的每个元素 a[i][j]，对于每个位置 (i, j)，更新 dp[i][j] 有两种情况：
- 如果我们不包含当前元素，则 dp[i][j] = dp[i-1][j]，因为不包括元素意味着上一行或同一行的某个列组合。
- 如果我们包含当前元素，则 dp[i][j] = dp[i-1][j-a[i][j]] + dp[i][j-a[i][j]]，因为我们有两选择：要么不包含这个元素，要么包含并减少总和。

3. 最终答案：我们需要找到所有和小于等于 K 的非空子矩阵的数量，这可以通过 dp[N][K] 得到。

下面是 C++ 代码实现：

#include <vector>

int countSubmatrices(vector<vector<int>>& matrix, int K) {
    int N = matrix.size(), M = matrix[0].size();
    vector<vector<int>> dp(N+1, vector<int>(K+1, 0));
    
    // 初始化
    for (int i = 1; i <= N; i++) {
        dp[i][0] = 1;
    }
    for (int j = 1; j <= K; j++) {
        dp[0][j] = 0;
    }

    // 动态规划计算
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            dp[i][j] = dp[i-1][j];
            if (matrix[i-1][j-1] <= K) {
                dp[i][j] += dp[i-1][j-matrix[i-1][j-1]];
            }
        }
    }

    return dp[N][K];
}