题意:
给出两个长度不超过 \(50\) 的字符串 \(S, T\), 每次可以在 \(S\) 中插入一个字符, 把每次操作后的 \(S\) 写成一个序列, 问有多少种不同的序列.
注意到我们可以把 \(S\) 拆分成一段一段原序列 / 新增序列, 我们只需要统计出新增序列对应 \(T[l : r]\) 的方案数 \(g[l, r]\), 接下来枚举 \(S[i + 1]\) 匹配下一个位置 \(T[k]\),\(dp[i, j] \rightarrow g[j + 1, k - 1] \times dp[i + 1, k] \times \binom {k - i - 1} {j - i}, S[i + 1] = T[k]\).
我们枚举第一次新增的位置 \(k\),\(g[l, r] = \sum_{k} g[l, k - 1] \times g[k + 1, r] \times \binom {r - l} {k - l}\), 注意到这样可能会重复, 也就是 \(T[k] = T[r]\) 的情况, 不进行这样的转移就好了.因为我们转移的右半区间其实已经包含这种情况了 (这步挺厉害的
来源: http://www.bubuko.com/infodetail-2997357.html