题意分析

题目大意​：

给定一个$n × 3$ 的矩阵，已知：

$1$. 每行的和$row[1..n]$

$2$. 每列的和$c_1, c_2, c_3$ 要求计算满足这些条件的非负整数矩阵的数量，结果对$10^{17}$ 取模。如果行列和不匹配（即$sum(row) ≠ c_1 + c_2 + c_3）$，直接输出$0$。

关键点分析​：

​$1$. 行列和必须相等​：若$sum(row) ≠ c_1 + c_2+ c_3$，无解。

$2$. ​动态分配问题​：每行的三个数 $(x, y, z)$ 需要满足：

$(1)$ $x + y + z = row[i]$

$(2)$ $x ≥ 0, y ≥ 0, z ≥ 0$

$(3)$ 所有行的$x$之和为$c_1，y$之和为$c_2，z$之和为$c_3$。

解题思路

方法选择:

这是一个典型的多维动态规划（DP）​问题，状态表示已分配的部分列和，逐步填充矩阵的行。

状态定义：

设$dp[a][b]$表示： $1$. 已填充的 $c_1$ 列和为 $a$

$2$. 已填充的 $c_2$ 列和为 $b$

$3$. 则$c_3$ 列和为$total$_$row$$- a - b$（由行列和相等保证）

转移方程：

对于每一行$row[i]$，枚举其可能的分配$(x, y, z)$：

$1$. $x + y + z = row[i]$

$2$.$x ≤ c_1 - a$（剩余可分配的 $c_1$ 列和）

$3$. $y ≤ c_2 - b$（剩余可分配的 $c_2$ 列和）

$4$. $z ≤ c3 - ($$total$_$row - a - b)$（剩余可分配的 $c_3$ 列和）

更新状态：

$new$_$dp[a + x][b + y] += dp[a][b]$

初始化​：

$dp[0][0] = 1$（未填充任何行列时的初始状态）

结果​：

最终答案为 $dp[c1][c2]$（所有列和恰好分配完毕）。

标程：

#include <iostream>
#include <vector>
#include <algorithm>  // 包含min函数
#include <utility>    // 包含move函数
using namespace std;

typedef long long ll;
const ll MOD = 100000000000000000LL; // 1e17的精确表示

int main() {
    int n, c1, c2, c3;
    cin >> n >> c1 >> c2 >> c3;
    vector<int> row(n);
    int total_row = 0;
    for (int i = 0; i < n; ++i) {
        cin >> row[i];
        total_row += row[i];
    }

    if (total_row != c1 + c2 + c3) {
        cout << 0 << endl;
        return 0;
    }

    // dp[a][b]表示已分配c1列和a、c2列和b时的方案数
    vector<vector<ll> > dp(c1+1, vector<ll>(c2+1, 0));
    dp[0][0] = 1;

    for (int r = 0; r < n; ++r) {
        int s = row[r];
        vector<vector<ll> > new_dp(c1+1, vector<ll>(c2+1, 0));

        for (int a = 0; a <= c1; ++a) {
            for (int b = 0; b <= c2; ++b) {
                if (dp[a][b] == 0) continue;

                // 枚举当前行给三列的分配量
                for (int x = 0; x <= min(s, c1 - a); ++x) {
                    for (int y = 0; y <= min(s - x, c2 - b); ++y) {
                        int z = s - x - y;
                        if (z < 0 || z > c3) continue;

                        new_dp[a + x][b + y] = 
                            (new_dp[a + x][b + y] + dp[a][b]) % MOD;
                    }
                }
            }
        }
        dp = new_dp;  // 直接赋值替代move，兼容性更好
    }

    cout << dp[c1][c2] << endl;
    return 0;
}