CF今天好像挂了inqueue了评测都有5页。
下面的代码通过了校内OJ的测试，应该没什么问题，好像数据就是从CF上扒下来的来着
题解：
考虑合法的路径一定满足左边一个UUU，右边一个UUU，中间是蛇形。
枚举左边合法的UUU和中间的每个格子进行转移，f[0/1][i][j]f[0/1][i][j]f[0/1][i][j]表示当前在(0/1,i)(0/1,i)(0/1,i)这个格子，匹配了前jjj个的方案数。
统计答案考虑枚举右边的UUU就行了。
然后考虑反着再匹配一次。
注意一下要避免长度为222的重复统计，细节有点多。。。
代码：
#include<bits/stdc++.h>#definelllonglong#definereregister#definecsconstusingstd::cerr;usingstd::cout;typedefstd::pair<int,int>pii;#definefifirst#definesesecondcsintN=2e3+20,mod=1e9+7;inlineintadd(inta,intb){a+=b-mod;returna+(a>>31&mod);}inlineintdec(inta,intb){a-=b;returna+(a>>31&mod);}inlineintmul(inta,intb){llr=(ll)a*b;returnr>=mod?r%mod:r;}inlinevoidInc(int&a,intb){a+=b-mod;a+=a>>31&mod;}inlinevoidDec(int&a,intb){a-=b;a+=a>>31&mod;}inlinevoidMul(int&a,intb){a=mul(a,b);}csintbs1=5,bs2=1147859;intpw1[N],pw2[N];inlinevoidinit(){pw1[0]=pw2[0]=1;for(intrei=1;i<N;++i)pw1[i]=mul(pw1[i-1],bs1),pw2[i]=mul(pw2[i-1],bs2);}classHASH{private:chars[N];intpre1[N],pre2[N],suf1[N],suf2[N];public:intlen;charoperator[](into){returns[o];}voidread(){scanf("%s",s+1);len=strlen(s+1);for(intrei=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(intrei=len;i;--i){suf1[i]=add(mul(suf1[i+1],bs1),s[i]);suf2[i]=add(mul(suf2[i+1],bs2),s[i]);}}piiget(intl,intr){if(l<=r)returnpii(dec(pre1[r],mul(pre1[l-1],pw1[r-l+1])),dec(pre2[r],mul(pre2[l-1],pw2[r-l+1])));elsereturnpii(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;intn,m,ans;intf[2][N][N];signedmain(){#ifdefzxyoifreopen("string.in","r",stdin);#endifinit();s0.read(),s1.read(),t.read();n=s0.len,m=t.len;f[0][n+1][0]=f[1][n+1][0]=1;for(intrei=n;i;--i){f[0][i][0]=f[1][i][0]=1;for(intrek=2;k*2<=m&&i+k-1<=n;++k){autot1=s0.get(i,i+k-1),t2=s1.get(i,i+k-1);autot3=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(intrei=n;i;--i)for(intrek=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(intrei=1;i<=n+1;++i){Inc(ans,f[0][i][m]);Inc(ans,f[1][i][m]);for(intrek=2;k*2<=m&&k<i;++k){autot1=s0.get(i-k,i-1),t2=s1.get(i-k,i-1);autot3=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";return0;}memset(f,0,sizeoff);f[0][n+1][0]=f[1][n+1][0]=1;for(intrei=n;i;--i){f[0][i][0]=f[1][i][0]=1;for(intrek=2;k*2<m&&i+k-1<=n;++k){autot1=s0.get(i,i+k-1),t2=s1.get(i,i+k-1);autot3=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(intrei=n;i;--i){for(intrek=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(intrei=1;i<=n+1;++i){Inc(ans,f[0][i][m]);Inc(ans,f[1][i][m]);for(intrek=2;k+k<m&&k<i;++k){autot1=s0.get(i-k,i-1),t2=s1.get(i-k,i-1);autot3=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";return0;}
