统计超序列：题解

思路

从左到右贪心匹配固定序列 $a$。若当前已经匹配了前 $j$ 项，则恰有一个值 $a_{j+1}$ 会使状态前进，其余 $k-1$ 个值保持状态不变。因此答案只与 $n,m,k$ 有关，与 $a$ 的具体内容无关。

总共有 $k^m$ 个长度为 $m$ 的序列。一个序列不包含 $a$，当且仅当贪心过程最终只匹配了 $j<n$ 项。固定恰好前进的 $j$ 个位置，有 $\binom mj$ 种选择；其余 $m-j$ 个位置各有 $k-1$ 种不会前进的取值。因此坏序列数为

$$\sum_{j=0}^{n-1}\binom mj(k-1)^{m-j}.$$

所求答案为

$$k^m-\sum_{j=0}^{n-1}\binom mj(k-1)^{m-j}\pmod{10^9+7}.$$

因为 $m<10^9+7$，可以用

$$\binom m{j+1}=\binom mj\frac{m-j}{j+1}$$

在线性时间递推组合数。$k=1$ 时只有全一序列，答案直接为一。

做法

• 子任务 1：枚举全部 $k^m$ 个候选序列并检查 $a$ 是否为其子序列。
• 子任务 2：维护 $0\ldots n$ 个贪心匹配状态，逐位置转移，复杂度 $O(nm)$。
• 子任务 3：计算总数减去上述组合补集，复杂度 $O(n+\log m)$。

正确性证明

引理 1：对任意尚未完整匹配的状态 $j$，一个新元素恰有一种取值使状态变为 $j+1$，另有 $k-1$ 种取值使状态保持 $j$。

贪心下一项必须等于固定值 $a_{j+1}$；值域内只有这个值相等，其余值均不相等。

引理 2：最终恰好匹配 $j<n$ 项的序列数为 $\binom mj(k-1)^{m-j}$。

选择发生状态前进的 $j$ 个位置后，这些位置的取值被唯一确定；由引理 1，其余位置各有 $k-1$ 种不前进的取值，且这些选择唯一对应一个最终状态为 $j$ 的序列。

定理：算法输出包含 $a$ 作为子序列的长度为 $m$ 的序列数。

所有 $k^m$ 个序列分为完整匹配与最终匹配 $j<n$ 项两类。由引理 2，各个 $j$ 的坏序列集合互不相交，其和正是补集大小。总数减补集即为所求。

复杂度

每组测试时间复杂度 $O(n+\log m)$，空间复杂度 $O(1)$；所有测试合计满足 $O(\sum n+ t\log m)$。