菜王的 blog

赛时没敢开这个题，但是赛后单杀了。以后还是得相信自己，大胆开题啊。

首先考虑解决去掉“$b$ 不是子序列”这个限制，即下面的问题：

给定正整数 $n, m, k$，请你求出满足以下条件的值域为 $[1, k]$ 的整数序列 $a_{1 \sim n}$ 的个数：

• 所有长度为 $m$，值域为 $[1, k]$ 的整数序列都是 $a$ 的（不一定连续的）子序列。

先尝试快速判断是否合法，相当于我们需要尽量找到一个序列不在 $a$ 中出现。那么贪心的想，每次肯定是加入一个数使得这个数匹配到的位置最远。那么设当前匹配 $a$ 的位置为 $i$，下一个为 $j$，那么 $j$ 显然是满足 $[i + 1, j]$ 区间内 $1 \sim k$ 每个数都出现的最小位置，这样跳 $m$ 次如果还是没有跳出序列那么就合法。

所以我们顺带刻画了这个序列的结构，肯定至少是 $m$ 个完整的段拼起来，然后后面任意填。其中一“段"需要满足里面 $1 \sim k$ 每个数都出现，并且不存在一个更短的前缀满足该条件。一段的方案数是好算的，那么我们就做完了这个简单版问题。

回来解决原问题，我们迅速发现原序列肯定是在完整的 $m$ 段的基础上删掉最后一个数形成的。因为如果原序列至少有完整的 $m$ 段，那么一定可以匹配所有的序列。显然，这 $m$ 段中，第 $i$ 段的结尾一定是 $b_i$，否则若每一段组成的结尾组成的新序列 $c$（显然 $c \ne b$）若出现则 $b$ 必定出现。

我们发现这两个条件还不够，因为条件显然避免了 $b$ 的出现，但是又可能弄出了一个其它序列也无法出现。

此时我们要贪心的找一个序列 $c$ 使 $b \ne c$，但是 $c$ 也不在 $a$ 中出现。考虑一个策略：使 $c$ 恰好有一个位置和 $b$ 不同。显然该策略一定是不劣的，否则如果有多个位置 $c_p \ne b_p$ 且策略可以成功，只保留最后一个也是可以成功的。

而我们阻止该策略的方法就是，让每一段不匹配到最后的位置都无法直接跳到下一段的最后位置，比如 $[1, 2, 3, 4, 4, 5], [1, 2, 3, 5, 4]$，在第一段中不匹配到最后的位置，都会被倒数第二个位置给拦住。而只要匹配过程中在某一段匹配了大于一次就一定会在 $a$ 中出现，从而策略失败。

但是还有一个情况，如果对于一个 $p$ 有 $p = m$ 或 $b_p = b_{p + 1}$，那么就不需要额外添加位置拦住。

那么我们只需要分别对于两种段，分别算出其方案数，并卷起来即可。

对于 $p = m$ 或 $b_p = b_{p + 1}$ 的段，要满足该段最后一个位置是 $b_p$。

对于 $b_p \ne b_{p + 1}$ 的段，在上面的要求的基础上，还要满足 $b_{p + 1}$ 的最后一个位置满足：在该段内，它前面每种除 $b_p$ 之外的数都存在。

这两个都是容易算出的，所以原问题得以解决。

code