题解：P5784 [CQOI2008] 矩阵的个数

楼上的有些题解没有具体提到 dp 的状态转移这样优化是对的，以及为什么看似 TLE 的复杂度是对的。所以才诞生了这篇题解。

给定一个 $n×3$ 的矩阵的各行各列之和，求满足条件的矩阵的个数。 $1\le n\le 200$，每行每列之和均不超过 $125$。

这是一道技术题。这一类题主要有两种解决方式：

而我们要发现这题的一个特点：只有 $3$ 列。极有限的行数提示我们使用 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 复杂度 $\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，实则这是可以接受的。因为：