P8386 [PA2021] Od deski do deski
Solution
先考虑如何判定一个序列 \(a\) 是否合法。
记 \(dp_{i} = 0/1\) 表示考虑前 \(i\) 个数是否能被删空：\(dp_{i} \xleftarrow{\texttt{or}} dp_{j - 1}[a_i = a_j]\)。初始化 \(dp_{0} = 1\)。
类似地把判定性问题转成计数问题。
从前往后填数，由于合法状态与非法状态之间可以相互转化，所以我们要同时记录这两种情况的数量。
填数时要考察当前填多少个数合/非法，因此要记录这样一个信息：之前有多少不同的数值 \(x\)，使得存在 \(dp_{j - 1} = 1\) 且 \(a_j = x\)。
记 \(f_{i, j}\) 表示填完前 \(i\) 个数，所有 \(dp_{p - 1} = 1(p < i)\) 对应的 \(a_p\) 组成的数集大小为 \(j\) 的合法方案数，\(g_{i, j}\) 表示同样意义下的非法方案数。
\[\begin{aligned}
f_{i, j} &\leftarrow j \times f_{i - 1, j} \\
f_{i, j} &\leftarrow j \times g_{i - 1, j} \\
g_{i, j} &\leftarrow (m - j) \times g_{i - 1, j} \\
g_{i, j + 1} &\leftarrow (m - j) \times f_{i - 1, j} \\
\end{aligned}
\]
由于最后一个转移是由合法状态转移过来，并且当前位置上填了新的数值，因此数集的大小加一。
时间复杂度 \(O(n\times \min(n, m))\)。