ABC299F

· · 题解

这种计数题考虑 dp。

从 T 直接下手不太好办，我们考虑在 S 中找 TT。

首先我们枚举一下 TT 中间的分隔点 r。

设 f_{i, j} 表示 S_{1 \sim i} 的一个子序列组成了 T 且 S_{r + 1 \sim j} 的一个子序列组成了 T 的 TT 数量，于是有转移式：

f_{i, j} \leftarrow f_{i, j} + f_{a, b}\ (S_i = S_j, S_a = S_b, a < i, b < j)

但是这样很容易计算到重复的贡献，于是我们在转移的时候规定只能向后继转移，那么就有：

f_{nxt_{i, ch}, nxt_{j, ch}} \leftarrow f_{nxt_{i, ch}, nxt_{j, ch}} + f_{i, j}\ (S_i = S_j)

其中 nxt_{i, ch} 表示 S_i 的下一个 ch 字符。

为了防止重复计算答案，初始状态下，f_{nxt_{0, ch}, nxt_{r, ch}} = 1，答案是对每次 f_{r, j} 求和。

Code：https://atcoder.jp/contests/abc299/submissions/40914040。