CF613E Puzzle Lover 题解

作者: xht37 分类: 题解 发布时间: 2020-02-12 20:11

Visits: 228

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注