题解 CF613E 【Puzzle Lover】
xht
2020-02-12 22:55:09
> [CF613E Puzzle Lover](https://codeforces.com/contest/613/problem/E)
## 题意
- 给定一个 $2 \times n$ 的矩阵，每个位置上有一个小写字母。
- 有一个长度为 $k$ 的小写字符串 $w$，询问矩阵中有多少条有向路径满足以下条件：
- 路径上的字母连起来恰好为 $w$。
- 不多次经过同一个位置。
- 只能向上下左右四个方向走。
- $n,k \le 2 \times 10^3$，答案对 $10^9+7$ 取模。
## 题解
假设 $n,k$ 同阶。
考虑**头尾不在同一列**的情况，不妨设头在尾的左侧。对于头在尾的右侧的情况，可以将 $w$ 翻转之后在求一遍。
当头在尾的左侧时，我们将路径划分成连续的三个部分：
1. 头所在的列及其左侧的部分；
2. 在头的右侧尾的左侧的部分；
3. 尾所在的列及其右侧的部分。
对于任意一条路径，它的第 $1/3$ 部分都肯定非空，而第 $2$ 部分可能为空。
下面我们依次考虑每一个部分：
1. 这部分要么是一个格子，要么是一个 U 字形，我们可以对于每个格子求出「若第 $1$ 部分在这个格子结束，所有可能的第 $1$ 部分的长度」，借助 Hash 即可做到 $\mathcal O(n^2)$。
2. 这部分不能往左，考虑 dp，设 $f_{i,j,k}$ 表示「若第 $2$ 部分在 $(i,j)$ 结束，上一个格子为 $(i,j-1)$，且第 $1,2$ 部分的长度和为 $k$ 的方案数」，设 $g_{i,j,k}$ 表示「若第 $2$ 部分在 $(i,j)$ 结束，上一个格子其同一列，且第 $1,2$ 部分的长度和为 $k$ 的方案数」，从左到右转移，转移时枚举下一个格子即可，时间复杂度为 $\mathcal O(n^2)$。
3. 与第 $1$ 部分一样，对于每个格子求出「若第 $3$ 部分从这个格子开始，所有可能的第 $3$ 部分的长度」，然后与第 $2$ 部分接上，即第 $2$ 部分的结束的格子的右边一个格子就是第 $3$ 部分开始的格子，同样借助 Hash 可以做到 $\mathcal O(n^2)$。
还剩下**头尾在同一列**的情况，可以发现我们直接在考虑第 $1/3$ 部分时顺便解决掉就好了，注意翻转前后会重复计算一次，最后除掉就好了。
总时间复杂度 $\mathcal O(n^2)$。
## 代码
```cpp
#define Hash pair<modint, modint>
const Hash B = mp(131, 13331);
inline Hash operator + (Hash a, Hash b) { return mp(a.fi + b.fi, a.se + b.se); }
inline Hash operator - (Hash a, Hash b) { return mp(a.fi - b.fi, a.se - b.se); }
inline Hash operator * (Hash a, Hash b) { return mp(a.fi * b.fi, a.se * b.se); }
inline Hash operator + (Hash a, int b) { return mp(a.fi + b, a.se + b); }
const int N = 2e3 + 7;
int n, m;
char s[3][N];
modint f[2][N][N], g[2][N][N], ans, now;
Hash p[N], h[2][3][N];
bool a[2][N][N], b[2][N][N];
inline Hash H(int o, int i, int l, int r) {
if (!o) return h[o][i][r] - h[o][i][l-1] * p[r-l+1];
return h[o][i][l] - h[o][i][r+1] * p[r-l+1];
}
inline bool pd(int o, int i, int j, int k) {
if (!o) {
if (j < k) return 0;
if (H(1, i ^ 1, j - k + 1, j) != H(0, 2, 1, k)) return 0;
if (H(0, i, j - k + 1, j) != H(0, 2, k + 1, 2 * k)) return 0;
return 1;
}
if (j + k - 1 > n) return 0;
if (H(0, i, j, j + k - 1) != H(0, 2, m - 2 * k + 1, m - k)) return 0;
if (H(1, i ^ 1, j, j + k - 1) != H(0, 2, m - k + 1, m)) return 0;
return 1;
}
inline void solve() {
for (int i = 1; i <= m; i++) h[0][2][i] = h[0][2][i-1] * B + s[2][i];
for (int i = 0; i <= 1; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= m; k++) {
f[i][j][k] = g[i][j][k] = 0;
if (k == 1) {
g[i][j][k] = a[i][j][k] = s[i][j] == s[2][1];
b[i][j][k] = s[i][j] == s[2][m];
} else if (!(k & 1)) {
g[i][j][k] = a[i][j][k] = pd(0, i, j, k / 2);
b[i][j][k] = pd(1, i, j, k / 2);
}
if (k == m) {
now += a[i][j][k];
if (m > 2) now += b[i][j][k];
}
}
dbg(ans.x);
for (int j = 1; j <= n; j++)
for (int k = 1; k <= m; k++) {
for (int i = 0; i <= 1; i++)
if (s[i][j] == s[2][k])
f[i][j][k] += f[i][j-1][k-1] + g[i][j-1][k-1];
for (int i = 0; i <= 1; i++)
if (s[i][j] == s[2][k])
g[i][j][k] += f[i^1][j][k-1];
for (int i = 0; i <= 1; i++)
if (b[i][j+1][m-k])
ans += f[i][j][k] + g[i][j][k];
}
}
int main() {
rds(s[0], n), rds(s[1], n), rds(s[2], m), p[0] = mp(1, 1);
for (int i = 1; i <= max(n, m); i++) p[i] = p[i-1] * B;
for (int i = 0; i <= 1; i++) {
for (int j = 1; j <= n; j++)
h[0][i][j] = h[0][i][j-1] * B + s[i][j];
for (int j = n; j; j--)
h[1][i][j] = h[1][i][j+1] * B + s[i][j];
}
solve(), reverse(s[2] + 1, s[2] + m + 1), solve(), print(ans + now / 2);
return 0;
}
```