题解：P5784 [CQOI2008] 矩阵的个数
ziga
·
·
题解
背景
楼上的有些题解没有具体提到 dp 的状态转移这样优化是对的，以及为什么看似 TLE 的复杂度是对的。所以才诞生了这篇题解。
题意
给定一个 n×3 的矩阵的各行各列之和，求满足条件的矩阵的个数。
## 思路
这是一道技术题。这一类题主要有两种解决方式：
- 数学，排列组合
- 计数型 dp。
而我们要发现这题的一个特点：只有 $3$ 列。极有限的行数提示我们使用 dp。因为使用 dp 的条件是状态有限。
## 朴素 dp
$a_i$ 表示第 $i$ 行的和。
$f_{i,c_1,c_2,c_3}$ 表示处理：前 $i$ 行，每列的和分别是 $c_1,c_2,c_3$ 的矩阵个数。
那么一个 dp 状态是合法的，当且仅当：$$c_1+c_2+c_3=\sum_{i=1}^na_i$$
枚举在第 $i$ 行会填入的三个非负整数 $s_{i,1},s_{i,2},s_{i,3}$。要求：$$s_{i,1}+s_{i,2}+s_{i,3}=a_i$$
状态转移方程 $$f_{i,c_1,c_2,c_3}=\sum f_{i-1,c_1-s_{i,1},c_2-s_{i,2},c_3-s_{i,3}}$$。
初始 $f_{0,0,0,0}$ 为 $1$，其余为 $0$。
目标 $f_{n,C_1,C_2,C_3}$。
## 对 dp 优化
朴素 dp 复杂度 $\mathcal{O}(n\cdot V^6)$（$V$ 表示值域），这是远远不能接受的。为了减少复杂度，我们要裁剪冗余状态和转移。
前面谈到 $c_1+c_2+c_3$ 为定值，$s_{i,1}+s_{i,2}+s_{i,3}$ 也是定值。所以我们在每次枚举 $c$ 和 $s$ 时有很多是不合法的状态。
因此我们只枚举 $c_1,c_2,s_{i,1},s_{i,2}$，当 $c_1,c_2,s_{i,1},s_{i,2}$ 确定时，$c_3,s_{i,3}$ 也随之确定了。
所以令 $f_{i,c_1,c_2}$ 表示处理：前 $i$ 行，每列的和分别是 $c_1,c_2$ 的矩阵个数。
状态转移方程 $f_{i,c_1,c_2}=\sum f_{i-1,c_1-s_{i,1},c_2-s_{i,2}}$。
初始 $f_{0,0,0}$ 为 $1$，其余为 $0$。
目标 $f_{n,C_1,C_2}$。
时间复杂度 $\mathcal{O}(n\cdot V^2\cdot (a_i^2))$。
空间复杂度 $\mathcal{O}(n\cdot V^2)$。
看似 TLE，实则这是可以接受的。因为：
$$\begin{aligned}
n\cdot V^2\cdot(a_i^2) \
&= V^2\cdot (\sum a_i^2) \\
&\le V^2\cdot(\sum a_i)^2 \\
&=V^2\cdot V^2=V^4
\end{aligned}$$
其中 $V \le 125$，因此 $V^4 \approx 2\times 10^8$ 在可接受范围内，可过此题。
这其实这是一个小 trick，因为 $\sum a_i$ 与 $c_1+c_2+c_3$ 的量级是相等的。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long // 需要开 long long
const int N = 210, M = 1e17;
int n, c[10], a[N], f[N][N][N];
signed main() {
cin >> n >> c[1] >> c[2] >> c[3]; int tot = 0; // tot 表示 a 数组的和
for (int i = 1;i <= n;i ++) cin >> a[i], tot += a[i];
if (tot != c[1] + c[2] + c[3]) return cout << 0, 0; // 检查总和是否匹配，不匹配直接输出0
f[0][0][0] = 1; // 初始化
for (int i = 1;i <= n;i ++) {
for (int u = 0;u <= c[1];u ++) {
for (int v = 0;v <= c[2];v ++) {
// 第三列的值由 a[i]-s-t 确定
for (int s = 0;s <= a[i] && s <= u;s ++) {
for (int t = 0;t + s <= a[i] && t <= v;t ++) {
f[i][u][v] = (f[i][u][v] + f[i - 1][u - s][v - t]) % M;// 状态转移
}
}
}
}
}
cout << f[n][c[1]][c[2]];
}
```
### 总结
本题通过**减少状态维度**，利用约束条件优化了动态规划，将原本 $\mathcal{O}(nV^6)$ 的复杂度优化到 $\mathcal{O}(nV^4)$，在给定的数据范围内可以通过。关键在于发现行和与列和的**固定关系**，从而减少需要枚举的状态。
::::info[AI 使用说明]
此题解在写作完成后使用 DeepSeek 进行了检查和润色。
::::