【排列 DP】20260923C 覆色

有 $n$ 个从左到右排成一行的格子，初始时均未染色。你需要依次执行 $m$ 次操作。第 $i$ 次操作中，你选择两个相邻的格子，将它们都染成颜色 $i$；若格子已经有颜色，则原来的颜色会被覆盖。求出经过全部操作后，没有格子未染色的不同颜色序列有多少种。

$n\le 4000$，$m\le 1\times {10}^8$。

可以想到颜色不是需要最先考虑的，因为他会将序列划分成若干个长度为 $[1,2]$ 的段，然后选些颜色染段就行了。

接下来要分析段的特征，对于 $K$ 段使用 $[1,K]$ 进行研究，从排列 DP 的角度，观察最大值的特征。

当插入 $i$ 时，他只能是一个长为 $2$ 的段，因为他是当前的最大值，他可以取代掉之前的一个最大值段，也可以随意的插入进两个段之间成为一个新的最大值段，因此设 $f_{i,j}$ 表示 $i$ 个段有 $j$ 个最大值

$$f_{i,j}\leftarrow 2j\times f_{i-1,j}+(i-2(j-1))f_{i-1,j-1}$$

接下来选取颜色，由于最大值必然出现，因此实际上只能选择 $(\genfrac{}{}{0ex}{}{m-1}{i-1})$ 个颜色，接着还要分配长度，这 $i$ 段的长度至少得是 $1$ 先，然后 $j$ 个最大值长度必然为 $2$，因此剩下有 $i-j$ 段和 $n-i-j$ 个格子，组合数选取即可。