CF613E Puzzle Lover 题解

CF613E Puzzle Lover

题意

• 给定一个 $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)$。

代码

#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;
}