传送门

---

CF今天好像挂了in queue了评测都有5页。

下面的代码通过了校内OJ的测试，应该没什么问题，好像数据就是从CF上扒下来的来着

题解：

考虑合法的路径一定满足左边一个$U$，右边一个$U$，中间是蛇形。

枚举左边合法的$U$和中间的每个格子进行转移，$f[0/1][i][j]$表示当前在$(0/1,i)$这个格子，匹配了前$j$个的方案数。

统计答案考虑枚举右边的$U$就行了。

然后考虑反着再匹配一次。

注意一下要避免长度为$2$的重复统计，细节有点多。。。

---

代码：

#include<bits/stdc++.h> #define ll long long #define re register #define cs const using std::cerr; using std::cout; typedef std::pair<int,int> pii; #define fi first #define se second cs int N=2e3+20,mod=1e9+7; inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);} inline int dec(int a,int b){a-=b;return a+(a>>31&mod);} inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;} inline void Inc(int &a,int b){a+=b-mod;a+=a>>31&mod;} inline void Dec(int &a,int b){a-=b;a+=a>>31&mod;} inline void Mul(int &a,int b){a=mul(a,b);} cs int bs1=5,bs2=1147859; int pw1[N],pw2[N]; inline void init(){ pw1[0]=pw2[0]=1; for(int re i=1;i<N;++i) pw1[i]=mul(pw1[i-1],bs1), pw2[i]=mul(pw2[i-1],bs2); } class HASH{ private: char s[N]; int pre1[N],pre2[N],suf1[N],suf2[N]; public: int len; char operator[](int o){return s[o];} void read(){ scanf("%s",s+1);len=strlen(s+1); for(int re i=1;i<=len;++i){ pre1[i]=add(mul(pre1[i-1],bs1),s[i]); pre2[i]=add(mul(pre2[i-1],bs2),s[i]); } for(int re i=len;i;--i){ suf1[i]=add(mul(suf1[i+1],bs1),s[i]); suf2[i]=add(mul(suf2[i+1],bs2),s[i]); } } pii get(int l,int r){ if(l<=r) return pii(dec(pre1[r],mul(pre1[l-1],pw1[r-l+1])),dec(pre2[r],mul(pre2[l-1],pw2[r-l+1]))); else return pii(dec(suf1[r],mul(suf1[l+1],pw1[l-r+1])),dec(suf2[r],mul(suf2[l+1],pw2[l-r+1]))); } }s0,s1,t; int n,m,ans; int f[2][N][N]; signed main(){ #ifdef zxyoi freopen("string.in","r",stdin); #endif init(); s0.read(),s1.read(),t.read(); n=s0.len,m=t.len; f[0][n+1][0]=f[1][n+1][0]=1; for(int re i=n;i;--i){ f[0][i][0]=f[1][i][0]=1; for(int re k=2;k*2<=m&&i+k-1<=n;++k){ auto t1=s0.get(i,i+k-1),t2=s1.get(i,i+k-1); auto t3=t.get(m,m-k+1),t4=t.get(m-k*2+1,m-k); if(t1==t3&&t2==t4)f[1][i][k*2]=1; if(t2==t3&&t1==t4)f[0][i][k*2]=1; } } for(int re i=n;i;--i) for(int re k=1;k<=m;++k){ if(s0[i]==t[m-k+1])Inc(f[0][i][k],f[0][i+1][k-1]); if(s1[i]==t[m-k+1])Inc(f[1][i][k],f[1][i+1][k-1]); if(k>1&&s0[i]==t[m-k+1]&&s1[i]==t[m-k+2])Inc(f[0][i][k],f[1][i+1][k-2]); if(k>1&&s1[i]==t[m-k+1]&&s0[i]==t[m-k+2])Inc(f[1][i][k],f[0][i+1][k-2]); } for(int re i=1;i<=n+1;++i){ Inc(ans,f[0][i][m]); Inc(ans,f[1][i][m]); for(int re k=2;k*2<=m&&k<i;++k){ auto t1=s0.get(i-k,i-1),t2=s1.get(i-k,i-1); auto t3=t.get(k,1),t4=t.get(k+1,k*2); if(t1==t3&&t2==t4)Inc(ans,f[1][i][m-2*k]); if(t2==t3&&t1==t4)Inc(ans,f[0][i][m-2*k]); } } if(m==1){ cout<<ans<<"\n"; return 0; } memset(f,0,sizeof f); f[0][n+1][0]=f[1][n+1][0]=1; for(int re i=n;i;--i){ f[0][i][0]=f[1][i][0]=1; for(int re k=2;k*2<m&&i+k-1<=n;++k){ auto t1=s0.get(i,i+k-1),t2=s1.get(i,i+k-1); auto t3=t.get(1,k),t4=t.get(k*2,k+1); if(t1==t3&&t2==t4)f[1][i][k*2]=1; if(t2==t3&&t1==t4)f[0][i][k*2]=1; } } for(int re i=n;i;--i){ for(int re k=1;k<=m;++k){ if(s0[i]==t[k])Inc(f[0][i][k],f[0][i+1][k-1]); if(s1[i]==t[k])Inc(f[1][i][k],f[1][i+1][k-1]); if(m>2&&k>1&&s0[i]==t[k]&&s1[i]==t[k-1])Inc(f[0][i][k],f[1][i+1][k-2]); if(m>2&&k>1&&s1[i]==t[k]&&s0[i]==t[k-1])Inc(f[1][i][k],f[0][i+1][k-2]); } } for(int re i=1;i<=n+1;++i){ Inc(ans,f[0][i][m]); Inc(ans,f[1][i][m]); for(int re k=2;k+k<m&&k<i;++k){ auto t1=s0.get(i-k,i-1),t2=s1.get(i-k,i-1); auto t3=t.get(m-k+1,m),t4=t.get(m-k,m-k*2+1); if(t1==t3&&t2==t4)Inc(ans,f[1][i][m-k*2]); if(t2==t3&&t1==t4)Inc(ans,f[0][i][m-k*2]); } } cout<<ans<<"\n"; return 0; }