题目描述

我们需要统计满足特定条件的 $N \times N$ 方阵的数量。条件如下：
1. 方阵的所有元素都是非负整数。
2. 方阵的每一行的元素之和都等于 $L$。
3. 方阵的每一列的元素之和都等于 $L$。

其中，$N$ 是方阵的阶数 ($2 \le N \le 4$)，$L$ 是指定的行/列和 ($2 \le L \le 9$)。

样例

输入:
7 3

输出:
666

说明：统计所有 $3 \times 3$ 的非负整数矩阵，且每行、每列元素和都为 7 的矩阵数量，结果为 666。

算法1 (深度优先搜索 DFS + 回溯)

时间复杂度：指数级别，但在小规模数据下可行

思路分析

我们可以将问题看作是在 $N \times N$ 的网格中填入数字，并满足行和与列和的约束。一个自然的想法是逐个单元格地填数，并使用深度优先搜索（DFS）来探索所有可能的填法。

1. 状态定义: dfs(i, j) 表示当前正在尝试填充第 i 行、第 j 列的单元格 g[i][j]。我们需要维护两个辅助数组：rs[N] 存储当前各行的部分和，cs[N] 存储当前各列的部分和。

2. 递归过程:

   • 当前单元格 (i, j): 我们需要决定在这个单元格放入什么非负整数 x。
   • 约束: 放入的数 x 必须满足：
     • 非负：$x \ge 0$。
     • 行和约束：当前行 i 已经填入的数的和 rs[i] 加上 x 不能超过目标和 L，即 $rs[i] + x \le L$。
     • 列和约束：当前列 j 已经填入的数的和 cs[j] 加上 x 不能超过目标和 L，即 $cs[j] + x \le L$。
     • 因此，x 的取值范围是 $0 \le x \le \min(L - rs[i], L - cs[j])$。
   • 特殊处理：行末单元格: 当我们填充到某一行的最后一个单元格时，即 j == n - 1，为了满足该行的和为 L，这个单元格的值是唯一确定的，必须为 $x = L - rs[i]$ (此时 rs[i] 是前 n-1 个元素的和)。我们需要额外检查：
     • 这个确定的值 $x$ 是否非负 ($x \ge 0$)？
     • 这个值 $x$ 是否满足列和约束 ($cs[j] + x \le L$)？
     • 如果都满足，则可以填入 x 并继续搜索下一行；否则，当前路径无效，回溯。
   • 递归: 对于每个合法的 x 值：
     1. 将 x 填入 g[i][j]。
     2. 更新行和与列和：rs[i] += x, cs[j] += x。
     3. 计算下一个要填充的单元格坐标 (ni, nj)。如果 j == n - 1，则 ni = i + 1, nj = 0；否则 ni = i, nj = j + 1。
     4. 递归调用 dfs(ni, nj)。
     5. 回溯: 递归返回后，需要撤销当前步骤的操作，以便尝试其他可能的 x 值：rs[i] -= x, cs[j] -= x。
   • 递归边界 (Base Case): 当我们成功填充完所有 $N \times N$ 个单元格时（例如，当 i == n 时），我们需要进行最终的检查：
     • 所有行和在填充过程中已经通过特殊处理行末单元格或者迭代保证了（如果不是行末，迭代保证了 $rs[i] \le L$）。在行末，我们强制 $rs[i]$ 恰好等于 $L$。
     • 我们还需要检查所有列和是否都恰好等于 $L$。即检查 cs[k] == l 对于所有的 $k \in [0, n-1]$ 是否成立。
     • 如果所有列和也都等于 $L$，说明找到了一个满足条件的矩阵，将计数器 cnt 加 1。

3. 初始调用: 从 dfs(0, 0) 开始搜索。

4. 复杂度: 搜索树的分支因子取决于 $L$ 和当前的行/列和，深度为 $N^2$。虽然理论上界很高，但由于 $N$ 和 $L$ 非常小，行和与列和的约束会大大剪枝搜索空间，使得该方法在给定数据范围内可行。

C++ 代码

#pragma GCC optimize("Ofast") // 开启 O3 优化
#pragma GCC optimize("unroll-loops") // 开启循环展开优化
#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    int l, n; // 输入目标和 L, 矩阵阶数 N
    cin >> l >> n;

    vector g(n, vector<int>(n)); // 存储当前构建的矩阵 (虽然 DFS 中没直接用，但可以用来查看结果)
    vector<int> rs(n), cs(n); // rs[i]: 第 i 行当前和, cs[j]: 第 j 列当前和
    i64 cnt = 0; // 计数器，存储满足条件的矩阵数量

    // 定义 DFS 函数 (使用 lambda 表达式和 auto&& self 实现递归)
    auto dfs = [&](auto &&self, int i, int j) -> void {
        // 递归边界：当 i == n 时，表示所有行都已尝试填充完毕
        if (i == n) {
            // 检查所有列的和是否都等于 l
            for (int k = 0; k < n; k++) {
                if (cs[k] != l) return; // 如果有任何一列和不等于 l，则此方案无效
            }
            // 所有行和（在填充行末时已保证）和列和都满足条件
            cnt++; // 计数器加 1
            return;
        }

        // 计算下一个要填充的单元格坐标 (ni, nj)
        int ni = i + (j + 1) / n; // 如果 j+1 到达 n，则行数 i 加 1
        int nj = (j + 1) % n;   // 列数 j 模 n

        // 特殊处理：当前单元格是行的最后一个单元格 (j == n - 1)
        if (j == n - 1) {
            // 计算为了使行和为 l，当前单元格必须填入的值 x
            int x = l - rs[i];
            // 检查 x 是否合法：非负，且加入后列和不超过 l
            if (x >= 0 && cs[j] + x <= l) {
                // g[i][j] = x; // 记录值 (可选)
                rs[i] += x; // 更新行和
                cs[j] += x; // 更新列和
                self(self, ni, nj); // 递归到下一个单元格
                // 回溯：撤销更新
                rs[i] -= x; 
                cs[j] -= x;
            }
            // 如果 x 不合法，则此路径无效，直接返回，不继续递归
        } else { // 非行末单元格
            // 遍历当前单元格 (i, j) 所有可能的取值 x
            // x 的上限是 L 减去当前行/列已有的和
            for (int x = 0; x <= min(l - rs[i], l - cs[j]); x++) {
                // g[i][j] = x; // 记录值 (可选)
                rs[i] += x; // 更新行和
                cs[j] += x; // 更新列和
                self(self, ni, nj); // 递归到下一个单元格
                // 回溯：撤销更新
                rs[i] -= x;
                cs[j] -= x;
            }
        }
    };

    // 从左上角 (0, 0) 开始 DFS
    dfs(dfs, 0, 0);
    // 输出最终计数
    cout << cnt << "\n";

    return 0;
}

算法2 (动态规划 DP)

时间复杂度：$O(N \times |\text{States}| \times |\text{Rows}| \times N)$，其中 $|\text{States}|$ 是 DP 状态数， $|\text{Rows}|$ 是合法行向量数。

思路分析

我们可以换一个角度思考，不是逐个单元格填充，而是逐行构建矩阵。使用动态规划来记录构建到某一行时，各列累积和的状态。

1. 状态定义:
   dp[i][mask] 表示已经填充了前 i 行（从第 0 行到第 i-1 行），并且各列的累积和由向量 mask = (cs[0], cs[1], ..., cs[N-1]) 表示时，有多少种不同的填充方法。其中 cs[k] 是第 k 列在前 i 行的元素之和。
   由于状态只依赖于前一行，我们可以使用滚动数组优化，只保留当前行和下一行的状态，例如 dp[0] 和 dp[1]。
   dp[current_row_index % 2][mask] 表示填充到 current_row_index - 1 行时，列和为 mask 的方案数。

2. 预计算:
   为了进行状态转移，我们需要知道所有可能的“合法行向量”。一个合法的行向量 r = (r[0], r[1], ..., r[N-1]) 必须满足：

   • $r[k] \ge 0$ for all $k$.
   • $\sum_{k=0}^{N-1} r[k] = L$.
     我们可以预先生成所有这样的合法行向量，存储在一个列表 rows 中。由于 $N, L$ 很小，合法行向量的数量 $\binom{L+N-1}{N-1}$ 不会很大 (例如 N=4, L=9 时为 220)。

3. 状态转移:
   假设我们已经计算出填充前 j 行的所有状态 dp[j % 2]。现在要计算填充前 j+1 行的状态 dp[(j + 1) % 2]。
   我们需要清空 dp[(j + 1) % 2]。
   然后，遍历 dp[j % 2] 中的每一个状态 (mask, cnt)：

   • mask 是前 j 行的列和向量。
   • cnt 是达到此状态的方案数。
   • 对于每一个预计算好的合法行向量 r：
     1. 尝试将行向量 r 作为第 j 行（0-indexed）添加到当前状态 mask。
     2. 计算新的列和向量 new_mask = mask + r (向量加法)。
     3. 检查 new_mask 是否合法：对于所有列 k，必须满足 new_mask[k] \le L。如果超过 L，说明添加这一行 r 后，某一列的和会超过目标值 L，这是不允许的。
     4. 如果 new_mask 合法，则将方案数 cnt 累加到下一个状态中：dp[(j + 1) % 2][new_mask] += cnt。

4. 状态表示:
   由于列和向量 mask 是一个 vector<int>，我们可以使用 std::map<std::vector<int>, i64> 来存储 DP 状态，其中键是列和向量 mask，值是对应的方案数 cnt。

5. 初始状态:
   在填充第 0 行之前（即 j=0），唯一的有效状态是所有列和都为 0。所以 dp[0][zero_mask] = 1，其中 zero_mask 是一个包含 N 个 0 的向量。

6. 最终答案:
   当完成 $N$ 次迭代（填充了所有 $N$ 行）后，我们需要查找最终状态 dp[N % 2] 中，列和向量恰好等于目标向量 target_mask = (L, L, ..., L) 的方案数。这个方案数就是最终答案。

C++ 代码

#pragma GCC optimize("Ofast") // 开启 O3 优化
#pragma GCC optimize("unroll-loops") // 开启循环展开优化
#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    int l, n; // 输入目标和 L, 矩阵阶数 N
    cin >> l >> n;

    // --- Step 1: 预计算所有可能的合法行向量 ---
    vector<vector<int>> rows; // 存储所有合法行向量
    vector<int> row(n); // 当前正在构建的行向量
    // 使用递归函数生成所有和为 l 的 n 元非负整数向量
    function<void(int, int)> gen_rows = [&](int sum, int idx) {
        // 递归边界：当填充到第 n 个位置时 (索引从 0 到 n-1)
        if (idx == n) {
            // 如果当前和恰好等于 l，说明找到了一个合法行向量
            if (sum == l) rows.push_back(row);
            return;
        }
        // 尝试在当前位置 idx 填入数字 x (从 0 到 l)
        for (int x = 0; x <= l; x++) {
            // 剪枝：如果当前和加上 x 已经超过 l，后续的 x 更大，不可能合法
            if (sum + x > l) break;
            row[idx] = x; // 填入 x
            gen_rows(sum + x, idx + 1); // 递归到下一个位置
        }
    };
    gen_rows(0, 0); // 从第 0 个位置开始生成

    // --- Step 2: DP 计算 ---
    // 使用 map 存储 DP 状态，键是列和向量 (vector<int>)，值是方案数 (i64)
    // dp[0] 和 dp[1] 用于滚动数组
    map<vector<int>, i64> dp[2]; 
    vector<int> zero_mask(n, 0); // 初始列和向量 (全 0)
    dp[0][zero_mask] = 1; // 初始状态：0 行，列和全 0，方案数为 1

    // 迭代 n 次，每次添加一行
    for (int j = 0; j < n; j++) {
        int cur = j % 2; // 当前 DP 状态索引
        int nxt = (j + 1) % 2; // 下一个 DP 状态索引
        dp[nxt].clear(); // 清空下一个状态 map，准备填充

        // 遍历当前状态 dp[cur] 中的所有 (列和向量 mask, 方案数 cnt) 对
        for (const auto& [mask, cnt] : dp[cur]) {
            // 尝试将每一个预计算的合法行向量 r 添加到当前状态
            for (const auto& r : rows) {
                vector<int> new_mask = mask; // 复制当前列和向量
                bool valid = true; // 标记新状态是否合法
                // 计算新的列和向量，并检查是否超出 L
                for (int k = 0; k < n; k++) {
                    new_mask[k] += r[k];
                    // 如果任何一列的和超过 L，则此行向量 r 不能用于此状态
                    if (new_mask[k] > l) {
                        valid = false;
                        break;
                    }
                }
                // 如果添加行向量 r 后，所有列和都不超过 L
                if (valid) {
                    // 将当前状态的方案数 cnt 累加到下一个状态的对应 new_mask 中
                    dp[nxt][new_mask] += cnt;
                }
            }
        }
    }

    // --- Step 3: 输出结果 ---
    // 目标状态：填充完 n 行后，所有列的和都恰好等于 l
    vector<int> target_mask(n, l); 
    // 输出目标状态对应的方案数。如果 map 中不存在 target_mask，则默认值为 0。
    cout << dp[n % 2][target_mask] << "\n";

    return 0;
}