Seq

$k=2$ 暴力是 $dp_{i, j}$ 表示 第一个串匹配到 $i$,第二个匹配到 $j$ 的方案数量 （$i$, $j$,不必匹配）。

但是，这没什么用处，发掘性质。

数据随机生成

这种题通法：

暴搜，乱搞，随机化

你可以先这样写一下：

for i in [1, 5]
  for j in [1, 1000]
    随机生成一个 [1, 1000] 的整数并输出

你会惊奇的发现，每个元素在同一序列中出现次数很少。

于是，我们不妨换个角度，仍考虑 $k=2$ 只是发现，其实这等价于。

有若干个 $k$ 元组满足 $(a_1, \dots, a_k)$ 满足 $s_{1, a_1} = s_{2, a_2} = s_{3, a_3} \dots s_{k, a_k}$。

于是，你可以发现这样的元组不多，原问题变成五维偏序，$\mathcal{O}(n^2)$ DP 可以胜任。