Description
给定一个 \(2 \times n\) 的矩阵，每个位置上有一个小写字母。
有一个长度为 \(k\) 的小写字符串 \(w\)，询问矩阵中有多少条有向路径满足以下条件：
- 路径上的字母连起来恰好为 \(w\)。
- 不多次经过同一个位置。
- 只能向上下左右四个方向走。
\(n,k \le 2 \times 10^3\)，答案对 \(10^9+7\) 取模。
Solution
注意到矩阵的宽只有 \(2\)，所以最终的行走路线一定是这样：
即两边为一个 U 形，中间为一个不走回头路的路径和两边的 U 形拼接起来。
不妨先考虑起点在终点左边或者起点和终点在同一列并且起点先往左走的情况。
显然可以 dp，设 \(f_{i,j,s}\) 表示目前走到 \((i,j)\)，且匹配到了 \(w\) 的第 \(s\) 位的方案数，这个方案是考虑了左边的 U + 不回头路径或者只有不回头路径的方案。
那么如果 \((i,j)\) 右边能找到一个长度为 \(k-s\) 的 U 就可以让 \(f_{i,j,s}\) 更新答案。
实现时要注意不要算重。
时间复杂度：\(O(nk)\)。
Code