[PA2021] Od deski do deski

题目描述

题目传送门

思路

计数题，很容易想到 dp。

难点在于状态的设计，显然有一维状态是序列长度，有一维表示合法与否，dp 值表示为方案数，记为 $f_{i,{0/1}}$。

这样是没有办法转移的，因为我们接下来要填什么与之前填的数字有关，考虑加维。

发现对于一个合法序列 $S$，假设在后面加数字 $x$ 得到结果 $S+x$ 仍是合法的，不妨加一个维度表示加上后可以合法的数字数量。

设 $f_{i,,j,{0/1}}$ 表示长度为 $i$ 的序列，在后面加有 $j$ 种可以使得其合法的方案，当前合法与否。

$f_{i,j,1}$ 的转移

根据定义转移。

$$f_{i,j,1} = f_{i-1,j,1} \times j + f_{i-1,j,0} \times j$$

$f_{i,j,0}$ 的转移

根据定义，$f_{i,j,0}$ 是不合法的有两种加法：

在长度为 $i-1$ 的序列不合法序列结尾加上了不属于这 $j$ 种字符的答案，这样显然可以使序列变为合法的方案数不变。即：

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

另一种是在长度为 $i-1$ 的序列合法序列结尾加上了不属于这 $j$ 种字符的答案，这样会使序列变为合法的方案数加一，因为我们新加上的这个字符再加一个也能使序列合法。即：

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

时间复杂度 $\Theta(n^2)$，使用滚动数组，空间复杂度 $\Theta(n^2)$。