题解：CF1989E Distance to Different

> 称长度为 $n$ 的正整数序列 $a$ 是合法的，当且仅当 $1 \le a_i \le k$ 且 $1 \sim k$ 在 $a$ 中都有出现。
>
> 令 $b_i = \min_{a_j \ne a_i} |j-i|$。求所有合法 $a$ 对应的 $b$ 有多少种。
>
> $n \le 2 \times 10^5$，$k \le 10$。

~~这个 $k$ 的范围很诈骗啊。~~

考虑对于一个确定的 $a$，它的 $b$ 长什么样子。比如：

$$
a = \{\color{red}1,1,1,\color{blue}2,2,2,\color{green}3,\color{orange}4,\color{purple}5,5,5,5,5,\color{grey}6,6 \color{black}\} \\
b = \{\color{red}3,2,1,\color{blue}1,2,1,\color{green}1,\color{orange}1,\color{purple}1,2,3,2,1,\color{grey}1,2\}
$$

可以发现，除开头结尾外，每一个 $a$ 中长 $k$ 的极长连续段，在 $b$ 中都形如 $1,2,\dots,k/2,\dots,2,1$。而开头是 $k,k-1,\dots,1$，结尾是 $1,2,\dots,k$。

也就是说 $b$ 的形态只和 $a$ 中每个极长连续段的长度有关。

这里有一个小细节：如果 $a$ 中有长 $2$ 的极长连续段，那么对应到 $b$ 中是 $1,1$，这和**两个长 $1$ 的极长连续段**在效果上是相同的。而我们只需要计 $b$ 的形态数，所以我们在后续处理中，默认 **$a$ 中不存在长 $2$ 的极长连续段**。

别忘了还有一个限制是 $a$ 中 $1 \sim k$ 都出现过至少一次。不难发现，只要 $a$ 中的极长连续段**数量** $\ge k$ 就能满足这个条件。

于是可以愉快的 DP 啦！设 $f(i, j)$ 表示考虑前 $i$ 个位置，且 $i$ 是第 $j$ 个极长连续段的结尾。转移枚举上一个连续段的结尾的位置 $k$。注意**如果这一段不是第一段且不是最后一段**需要满足 $i-k \ne 2$。

答案为 $\sum_{j=k}^n f(n, j)$。因为段数要 $\ge k$。

转移可以前缀和优化成 $\mathcal O(1)$。但是状态数是 $\mathcal O(n^2)$ 的。考虑优化。

别忘了 $k$ 很小！所以求段数 $\ge k$ 复杂度不能接受，但是可以求段数 $<k$ 的方案数。用全集减一下就行。

这里的全集指 $\sum_{j=2}^n f(n,j)$。$j$ 从 $2$ 开始是因为**如果 $a$ 全部相同则 $b$ 无法定义**。

考虑怎么求全集。很简单，再做一遍上面的 DP，并直接把第二维去掉即可。

复杂度 $\mathcal O(nk)$。

- 前缀和优化前：<https://codeforces.com/contest/1989/submission/291168277>
- AC：<https://codeforces.com/contest/1989/submission/291168850>

正在渲染内容...