题目描述

题目传送门

思路

计数题,很容易想到 dp。

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

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

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

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

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

根据定义转移。

fi,j,1=fi1,j,1×j+fi1,j,0×jf_{i,j,1} = f_{i-1,j,1} \times j + f_{i-1,j,0} \times j

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

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

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

fi,j,0=fi1,j,0×(mj)f_{i,j,0} = f_{i-1,j,0} \times (m - j)

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

fi,j,0=fi1,j1,1×(mj)f_{i,j,0} = f_{i-1,j-1,1} \times (m - j)

时间复杂度 Θ(n2)\Theta(n^2),使用滚动数组,空间复杂度 Θ(n2)\Theta(n^2)