[Codeforces613E]Puzzle Lover

清疚 2021-12-17 10:01 201阅读 0赞

# Problem #

给你2\*n的格子，每个格子有一个字母，从任意一点出发，不重复的经过上下左右，生成要求的字符串。问有几种不同的走法。

# Solution #

![1232176-20171026082631254-1456300025.png][]  
分三段，左U型、中间、右U型。  
分别枚举左边和右边的长度，中间一段用Dp来解决。  
Dp\[i\]\[j\]\[k\]，i,j,k表示当前在(i,j)位置，枚举到第k个字符。

# Notice #

特殊情况下有重复。

# Code #

#include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define sqz main
    #define ll long long
    #define reg register int
    #define rep(i, a, b) for (reg i = a; i <= b; i++)
    #define per(i, a, b) for (reg i = a; i >= b; i--)
    #define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)
    const int INF = 1e9, mod = 1e9 + 7, Ha = 826036489, N = 2000;
    const double eps = 1e-6, phi = acos(-1.0);
    ll modd(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}
    ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}
    void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}
    char S[2][N + 5], st[N + 5];
    ll f[2][N + 5][N + 5], mi[N + 5];
    int n, m;
    void Calc(ll &X, ll Y)
    {
        X += Y;
        if (X >= mod) X -= mod;
    }
    struct Hash
    {
        ll hash[N + 5];
        void Make(int n, char *s)
        {
            hash[0] = 0;
            rep(i, 1, n) hash[i] = (hash[i - 1] * 31 + s[i] - 'a') % Ha;
        }
        ll Cut(int l, int r)
        {
            return (hash[r] - hash[l - 1] * mi[r - l + 1] % Ha + Ha) % Ha;
        }
    }pre[2], suf[2], Comp;
    ll Solve(int flag)
    {
        ll T = 0;
        memset(f, 0, sizeof(f));
        rep(j, 1, n)
        {
            f[0][j][0] = f[1][j][0] = 1;
            rep(i, 0, 1)
            {
                rep(k, 2, min(n - j + 1, m / 2))
                    if (Comp.Cut(m - 2 * k + 1, m - k) == pre[i].Cut(j, j + k - 1) && Comp.Cut(m - k + 1, m) == suf[1 - i].Cut(n - (j + k - 1) + 1, n - j + 1))
                        if (2 * k != m || flag) Calc(T, f[i][j][m - 2 * k]);
                rep(k, 2, min(j, m / 2))
                    if (Comp.Cut(k + 1, 2 * k) == pre[i].Cut(j - k + 1, j) && Comp.Cut(1, k) == suf[1 - i].Cut(n - j + 1, n - (j - k + 1) + 1))
                        if (2 * k != m || flag) Calc(f[i][j + 1][2 * k], 1);
            }
            rep(i, 0, 1)
                rep(k, 0, m - 1)
                    if (S[i][j] == st[k + 1])
                    {
                        Calc(f[i][j + 1][k + 1], f[i][j][k]);
                        if (k + 2 <= m && S[1 - i][j] == st[k + 2])
                            Calc(f[1 - i][j + 1][k + 2], f[i][j][k]);
                    }
            rep(i, 0, 1) Calc(T, f[i][j + 1][m]);
        }
        return T;
    }
    
    int sqz()
    {
        scanf("%s%s%s", S[0] + 1, S[1] + 1, st + 1);
        n = strlen(S[0] + 1), m = strlen(st + 1);
        mi[0] = 1;
        rep(i, 1, 2000) mi[i] = (mi[i - 1] * 31) % Ha;
        rep(i, 0, 1)
        {
            pre[i].Make(n, S[i]);
            reverse(S[i] + 1, S[i] + n + 1);
            suf[i].Make(n, S[i]);
            reverse(S[i] + 1, S[i] + n + 1);
        }
        Comp.Make(m, st);
        if (m == 1)
        {
            printf("%I64d\n", Solve(1) % mod);
            return 0;
        }
        ll ans = 0;
        Calc(ans, Solve(1));
        reverse(st + 1, st + m + 1);
        Comp.Make(m, st);
        Calc(ans, Solve(0));
        if (m == 2)
            rep(i, 1, n)
            {
                if (S[0][i] == st[1] && S[1][i] == st[2]) Calc(ans, mod - 1);
                if (S[1][i] == st[1] && S[0][i] == st[2]) Calc(ans, mod - 1);
            }
        printf("%I64d\n", ans);
        return 0;
    }

转载于:https://www.cnblogs.com/WizardCowboy/p/7735547.html

[1232176-20171026082631254-1456300025.png]: /images/20211217/afb01030ba004a3dae3f346e5dffedc4.png