资讯详情

题意

给出 \(n\) 个由 O 和 ~ 组成的字符串 \(s_i\)，还有 \(m\) 个额外字符串，第 \(n+i\) 个字符串 \(s_{n+i}\) 由第 \(s_x\) 和 \(s_y\) \((x,y<n+i)\) 个字符串拼接得到，即 \(s_{n+i}=s_x+s_y\)。你需要对这 \(n+m\) 个字符串解决以下问题：

有一只青蛙从字符串的起点出发，它只能站在 O 上，且每次可以向前跳 \(1\sim k\) 格，问跳到末尾有多少种不同的方案。

\(1\le n,m\le 10^5,1\le k\le 20,\sum|s_i|\le 10^5\)

思路

我们先对前 \(n\) 个 \(s_i\) 进行朴素 dp。设 \(f_{i}\) 为青蛙跳到第 \(i\) 格的方案数，显然有：

\[f_{i}=\begin{cases} 0 & s_i\neq 'O' \\ \sum_{j=\max(0,i-k)}^{i-1} f_{j} & s_i='O' \end{cases} \]

答案即为 \(f_{end}\)。

我们解决了前 \(n\) 个字符串的答案，考虑后 \(m\) 个字符串的答案。

假如把两段字符串拼接到一起，可以发现从一个字符串跳到另一个字符串只有可能从前一个字符串的最后 \(k\) 个位置跳到后一个字符串的前 \(k\) 个位置，所以我们对每个字符串不用存储太多的信息。

于是记 \(f_{i,s,t}\) 表示从第 \(i\) 个字符串的第 \(s\) 个字符开始，跳到距离末尾 \(t\) 个字符的位置的方案数。

前 \(n\) 个处理方法同上，对于后 \(m\) 个，用以上思路转移，则有：

\[f_{i,s,t}=\sum_{t',s'}^{s\le t',s'\le t,t'+s'+1\le k} f_{x,s,t'} f_{y,s',t} \]