题解归档 - cf613E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf613E
• 本地来源：problems/cf613E/idea.md
• 题目链接：https://codeforces.com/contest/613/problem/E
• 原始标题：CF613E Puzzle Lover

思路

CF613E Puzzle Lover

题意

$2 \times n$ 网格，每格一个小写字母。给定长度 $k$ 的单词 $w$。统计有多少条简单路径（格子两两不同、相邻格有公共边），路径上字母依次拼成 $w$。答案对 $10^9+7$ 取模。

思路

路径不能重复经过格子，在只有两行的网格里，任意合法路径可拆成三段：

1. 头：在某个格结束，形态为「单格」或「U 形」（先竖拐再沿一行走再竖拐回来）。
2. 身（蛇形）：只向右延伸，不回溯；DP 状态 f[row][col][len] 表示蛇形段在 (row,col) 结束、已匹配 len 个字符的方案数。
3. 尾：从下一列开始，形态同样是单格或 U 形。

固定「头在尾左侧」的方向做 DP；把 $w$ 反转再做一次，覆盖头在尾右侧的情况。同一列起止的 U 形路径会被算两次，在 work() 里用 now/2 修正；纯 U 形（整词就是来回）在正反两次 calc 里重复计数，用 reduce（$m=2$ 特判等）减掉。

蛇形转移（列 j 从左到右）：

• 从 (row, j-1) 横走：f[row][j+1][k] += f[row][j][k-1]（字母匹配时）。
• 从 (row^1, j) 竖走：f[row^1][j+1][k+1] += f[row][j][k-1]（连续两格匹配 $w[k],w[k+1]$）。

U 形头/尾用网格子串与 $w$ 的子串比较（正反哈希或直接比对均可），与蛇形 DP 衔接。

复杂度 $O(n \cdot m^2)$（U 形枚举 + 蛇形 DP），$n,m \le 2000$ 可过。

实现要点

• 输入有空行，用三次 scanf("%s") 读两行网格和单词即可。
• calc(1) 与反转 $w$ 后的 calc(0) 分别处理两种全局方向；m==2 时额外减去竖直两格路径的双重计数。
• U 形拼接时注意一行正向、另一行反向子串对齐（eqs / eqsf）。

结论

AC 解法：solution.cpp（蛇形 DP + 头尾 U 形 + 双向计数去重）。

参考

• Codeforces Round #339 Editorial — 613E

代码

来源：problems/cf613E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 06:13:01
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2005;
const ll mod=1000000007;
const ll mod2=1000000009;
const ll B1=131;
const ll B2=13331;
struct Hsh{
    ll a,b;
};
Hsh operator+(Hsh x,Hsh y){
    Hsh z;
    z.a=(x.a+y.a)%mod;
    z.b=(x.b+y.b)%mod2;
    return z;
}
Hsh operator+(Hsh x,ll y){
    Hsh z;
    z.a=(x.a+y)%mod;
    z.b=(x.b+y)%mod2;
    return z;
}
Hsh operator-(Hsh x,Hsh y){
    Hsh z;
    z.a=(x.a-y.a+mod)%mod;
    z.b=(x.b-y.b+mod2)%mod2;
    return z;
}
Hsh operator*(Hsh x,Hsh y){
    Hsh z;
    z.a=x.a*y.a%mod;
    z.b=x.b*y.b%mod2;
    return z;
}
Hsh operator*(Hsh x,ll y){
    Hsh z;
    z.a=x.a*y%mod;
    z.b=x.b*y%mod2;
    return z;
}
bool operator==(Hsh x,Hsh y){
    return x.a==y.a and x.b==y.b;
}
bool operator!=(Hsh x,Hsh y){
    return !(x==y);
}
Hsh pw[maxn+5],hf[2][maxn+5],hb[2][maxn+5],hw[maxn+5];
char gc[2][maxn+5],wc[maxn+5];
ll ncol,wlen,ans,now;
ll f[2][maxn+5][maxn+5],g[2][maxn+5][maxn+5];
bool aa[2][maxn+5][maxn+5],bb[2][maxn+5][maxn+5];
Hsh geth(ll o,ll i,ll l,ll r){
    if(i==2) return hw[r]-hw[l-1]*pw[r-l+1];
    if(o==0) return hf[i][r]-hf[i][l-1]*pw[r-l+1];
    return hb[i][l]-hb[i][r+1]*pw[r-l+1];
}
bool pd0(ll i,ll j,ll k){
    if(j<k) return 0;
    if(geth(1,i^1,j-k+1,j)!=hw[k]) return 0;
    if(geth(0,i,j-k+1,j)!=geth(0,2,k+1,2*k)) return 0;
    return 1;
}
bool pd1(ll i,ll j,ll k){
    if(j+k-1>ncol) return 0;
    if(geth(0,i,j,j+k-1)!=geth(0,2,wlen-2*k+1,wlen-k)) return 0;
    if(geth(1,i^1,j,j+k-1)!=geth(0,2,wlen-k+1,wlen)) return 0;
    return 1;
}
void work(){
    ll i,j,k,pd;
    memset(aa,0,sizeof(aa));
    memset(bb,0,sizeof(bb));
    for(i=1;i<=wlen;i++) hw[i]=hw[i-1]*Hsh{B1,B2}+(ll)(wc[i]-'a'+1);
    for(i=0;i<=1;i++)
        for(j=1;j<=ncol;j++)
            for(k=1;k<=wlen;k++){
                f[i][j][k]=g[i][j][k]=0;
                if(k==1){
                    pd=(gc[i][j]==wc[1]);
                    g[i][j][k]=pd;
                    aa[i][j][k]=pd;
                    bb[i][j][k]=(gc[i][j]==wc[wlen]);
                }else if((k&1)==0){
                    pd=pd0(i,j,k/2);
                    g[i][j][k]=pd;
                    aa[i][j][k]=pd;
                    bb[i][j][k]=pd1(i,j,k/2);
                }
                if(k==wlen){
                    now=(now+aa[i][j][k])%mod;
                    if(wlen>2) now=(now+bb[i][j][k])%mod;
                }
            }
    for(j=1;j<=ncol;j++)
        for(k=1;k<=wlen;k++){
            for(i=0;i<=1;i++)
                if(gc[i][j]==wc[k]){
                    f[i][j][k]=(f[i][j][k]+f[i][j-1][k-1]+g[i][j-1][k-1])%mod;
                }
            for(i=0;i<=1;i++)
                if(gc[i][j]==wc[k]){
                    g[i][j][k]=(g[i][j][k]+f[i^1][j][k-1])%mod;
                }
            for(i=0;i<=1;i++)
                if(bb[i][j+1][wlen-k]){
                    ans=(ans+f[i][j][k]+g[i][j][k])%mod;
                }
        }
}
int main(){
    ll i,j,zc;
    string s0,s1,wstr;
    cin>>s0>>s1>>wstr;
    ncol=(ll)s0.size();
    wlen=(ll)wstr.size();
    for(i=0;i<2;i++){
        for(j=1;j<=ncol;j++){
            if(i==0) gc[i][j]=s0[j-1];
            else gc[i][j]=s1[j-1];
        }
    }
    for(i=1;i<=wlen;i++) wc[i]=wstr[i-1];
    pw[0]=Hsh{1,1};
    for(i=1;i<=max(ncol,wlen);i++) pw[i]=pw[i-1]*Hsh{B1,B2};
    for(i=0;i<=1;i++){
        for(j=1;j<=ncol;j++) hf[i][j]=hf[i][j-1]*Hsh{B1,B2}+(ll)(gc[i][j]-'a'+1);
        for(j=ncol;j>=1;j--) hb[i][j]=hb[i][j+1]*Hsh{B1,B2}+(ll)(gc[i][j]-'a'+1);
    }
    ans=0;
    now=0;
    work();
    reverse(wstr.begin(),wstr.end());
    for(i=1;i<=wlen;i++) wc[i]=wstr[i-1];
    work();
    cout<<(ans+now/2)%mod<<endl;
    return 0;
}