自动搬运

查看原文

来自洛谷，原作者为

	lovelish 呜呜呜我不管宝宝就要装可爱qwq

搬运于2025-08-24 23:15:24，当前版本为作者最后更新于2025-03-20 18:25:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看到题目后，很容易想出使用动态规划，那么我们试着用动态规划解决该题。

发现数据范围比较小，于是我们不妨大胆一些定义状态。发现动态规划可以逐行转移，因为确定了前若干行的状态后，便不需要再更改，只需要再考虑后面的，无后效性。那么第一个维度就显然可以使用行数。

因为列与列之间没有明显的区分度，所以我们只能使用节点数定义第二维度。只定义该行的节点数显然是不够的，因为该行每一个节点的父节点选择是之前行的所有节点，因此第二维度定义为当前总节点数。

那么定义 $f_{i,j}$ 表示在 $i$ 行 $m$ 列的网格中，根节点在第一行且总节点数为 $j$ 个的总方案数。

边界很显然，当只有一个根节点时一共有 $m$ 种方案，即 $f_{i,1}=m$。

目标也很显然，所以情况相加即为答案：

$$\sum_{i=1}^n\sum_{j=1}^{n\times m}f_{i,j}$$

接下来我们看转移。

对于每一个 $f_{i,j}$，枚举第 $i$ 行的节点数量相加即可。当该行有 $k$ 个节点时，这 $k$ 个节点有不同的位置选择，即从 $m$ 个格子中选择 $k$ 个，即 $\binom{m}{k}$，对于每个节点而言，其可以选择任意一个之前行的节点作为自己的父亲，因为共有 $j-k$ 种选择，一共 $k$ 个节点，一共就是 $(j-k)^k$ 种选择。那么转移式即：

$$ f_{i,j}=\sum_{k=0}^{m}f_{i-1,j-k}\times \binom{m}{k}\times (j-k)^k $$

组合数和乘方参数都比较小，因此可以直接预处理出来。那么总时间复杂度即 $\mathcal O(n^2m^2)$。

于是该题就写完了，不过有一些小细节以及一些小常数优化，这里就不再说明。