传送门
考场上想分情况讨论+记忆化搜索,但情况有点多讨论不起
发现蛇的走法一定是这样(题解):
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define N 2010 #define ll long long #define ull unsigned long long //#define int long long int n, m; char mp[3][N], s[N]; const ll p=1e9+7, base=131; const int dlt[][2]={{-1,0},{1,0},{0,1},{0,-1}}; namespace force{ bool vis[3][N]; ll ans; void dfs(int x, int y, int back, int pos) { //cout<<"dfs "<<x<<' '<<y<<' '<<back<<' '<<pos<<endl; if (pos==m) {++ans; return ;} vis[x][y]=1; for (int i=0,x2,y2; i<4; ++i) if (i!=back) { x2=x+dlt[i][0], y2=y+dlt[i][1]; if (x2>=1&&x2<=2&&y2>=1&&y2<=n&&mp[x2][y2]==s[pos+1]&&!vis[x2][y2]) dfs(x2, y2, i^1, pos+1); } vis[x][y]=0; } void solve() { for (int i=1; i<=2; ++i) for (int j=1; j<=n; ++j) if (mp[i][j]==s[1]) dfs(i, j, 4, 1); //, cout<<"return "<<endl; printf("%lld\n", ans%p); exit(0); } } namespace task{ ll dp[2][N][N][2]; short hd[2][N][N], tail[2][N][N]; ull sh[N], h[3][N], b[N]; inline ull hashing(ull* h, int l, int r) {return h[r]-h[l-1]*b[r-l+1];} ll solve(bool op) { //cout<<double(sizeof(dp)+sizeof(hd))/1024/1024<<endl; memset(dp, 0, sizeof(dp)); memset(hd, 0, sizeof(hd)); memset(tail, 0, sizeof(tail)); b[0]=1; ll ans=0; for (int i=1; i<=n; ++i) b[i]=b[i-1]*base; for (int i=1; i<=m; ++i) sh[i]=sh[i-1]*base+s[i]; for (int i=1; i<=n; ++i) h[1][i]=h[1][i-1]*base+mp[1][i]; for (int i=1; i<=n; ++i) h[2][i]=h[2][i-1]*base+mp[2][i]; for (int i=1; i<=n; ++i) if (mp[1][i]==s[1]) { ++dp[0][i][1][0]; for (int j=i-1; j&&mp[1][j]==s[i-j+1]; --j) if (hashing(h[2], j, i)==hashing(sh, i-j+2, 2*i-2*j+2)) { if (2*i-2*j+2==m && (m!=2||op)) ++ans; else if (i<n && mp[2][i+1]==s[2*i-2*j+3]) { ++dp[1][i+1][2*i-2*j+3][0]; //, cout<<"1: "<<i<<' '<<j<<endl; ++tail[1][i][2*i-2*j+2]; } } } for (int i=1; i<=n; ++i) if (mp[2][i]==s[1]) { ++dp[1][i][1][0]; for (int j=i-1; j&&mp[2][j]==s[i-j+1]; --j) if (hashing(h[1], j, i)==hashing(sh, i-j+2, 2*i-2*j+2)) { if (2*i-2*j+2==m && (m!=2||op)) ++ans; else if (i<n && mp[1][i+1]==s[2*i-2*j+3]) { ++dp[0][i+1][2*i-2*j+3][0]; //, cout<<"2: "<<i<<' '<<j<<endl; ++tail[0][i][2*i-2*j+2]; } } } for (int i=1; i<=n; ++i) if (mp[1][i]==s[m]) { //cout<<"i: "<<i<<' '<<mp[1][i]<<' '<<s[m]<<endl; for (int j=i+1; j<=n&&mp[1][j]==s[m-j+i]; ++j) { //cout<<"j: "<<mp[1][j]<<' '<<s[m-j+i]<<endl; //cout<<i<<' '<<j<<' '<<m-2*j+2*i-1<<' '<<m-j+i-1<<endl; //cout<<hashing(h[2], i, j)<<' '<<hashing(sh, m-2*j+2*i-1, m-j+i-1)<<endl; if (hashing(h[2], i, j)==hashing(sh, m-2*j+2*i-1, m-j+i-1)) { //cout<<"check: "<<mp[2][i-1]<<' '<<s[m-2*j+2*i-2]<<' '<<m-2*j+2*i-1<<endl; if (2*j-2*i+2==m && (m!=2||op)) ; //cout<<"error1"<<endl; else if (i>1 && mp[2][i-1]==s[m-2*j+2*i-2]) ++hd[1][i-1][m-2*j+2*i-2]; //, cout<<3<<' '<<i<<' '<<j<<endl; } } } for (int i=1; i<=n; ++i) if (mp[2][i]==s[m]) { //cout<<"i: "<<mp[2][i]<<' '<<s[m]<<endl; for (int j=i+1; j<=n&&mp[2][j]==s[m-j+i]; ++j) { //cout<<"j: "<<mp[2][j]<<' '<<s[m-j+i]<<endl; //cout<<hashing(h[1], i, j)<<' '<<hashing(sh, m-2*j+2*i-1, m-j+i-1)<<endl; //cout<<i<<' '<<j<<' '<<m-2*j+2*i-1<<' '<<m-j+i-1<<endl; if (hashing(h[1], i, j)==hashing(sh, m-2*j+2*i-1, m-j+i-1)) { //cout<<"hash accepted "<<' '<<i<<' '<<mp[1][i-1]<<' '<<s[m-2*j+2*i-2]<<endl; if (2*j-2*i+2==m && (m!=2||op)) ; //cout<<"error2"<<endl; else if (i>1 && mp[1][i-1]==s[m-2*j+2*i-2]) ++hd[0][i-1][m-2*j+2*i-2]; //, cout<<4<<' '<<i<<' '<<j<<endl; } } } //cout<<"ans: "<<ans<<endl; #if 0 cout<<"ans: "<<ans<<endl; for (int i=1; i<=n; ++i) cout<<dp[0][i]<<' '; cout<<endl; for (int i=1; i<=n; ++i) cout<<dp[1][i]<<' '; cout<<endl; for (int i=1; i<=n; ++i) { cout<<dp[0][i]<<' '; for (int j=1; j<=m; ++j) cout<<dp[0][i][j][0]<<' '; cout<<endl; } for (int i=1; i<=n; ++i) { cout<<dp[1][i]<<' '; for (int j=1; j<=m; ++j) cout<<dp[1][i][j][0]<<' '; cout<<endl; } #endif for (int j=1; j<=n; ++j) for (int k=1; k<=m; ++k) { dp[0][j][k][1]=dp[0][j][k][0]; dp[1][j][k][1]=dp[1][j][k][0]; } for (int j=1; j<=n; ++j) { for (int k=1; k<=m; ++k) { #if 0 printf("dp[%d][%d][%d][%d]=%lld\n", 1, j, k, 0, dp[0][j][k][0]); printf("dp[%d][%d][%d][%d]=%lld\n", 1, j, k, 1, dp[0][j][k][1]); printf("dp[%d][%d][%d][%d]=%lld\n", 2, j, k, 0, dp[1][j][k][0]); printf("dp[%d][%d][%d][%d]=%lld\n", 2, j, k, 1, dp[1][j][k][1]); //cout<<"now ans="<<ans<<endl; #endif if (mp[1][j]==s[k]) { if ((m>2||op) && mp[2][j]==s[k+1]) dp[1][j][k+1][1]=(dp[1][j][k+1][1]+dp[0][j][k][0])%p; if (mp[1][j+1]==s[k+1]) { dp[0][j+1][k+1][1]=(dp[0][j+1][k+1][1]+dp[0][j][k][1])%p; dp[0][j+1][k+1][0]=(dp[0][j+1][k+1][0]+dp[0][j][k][1])%p; } } if (mp[2][j]==s[k]) { if ((m>2||op) && mp[1][j]==s[k+1]) dp[0][j][k+1][1]=(dp[0][j][k+1][1]+dp[1][j][k][0])%p; if (mp[2][j+1]==s[k+1]) { dp[1][j+1][k+1][1]=(dp[1][j+1][k+1][1]+dp[1][j][k][1])%p; dp[1][j+1][k+1][0]=(dp[1][j+1][k+1][0]+dp[1][j][k][1])%p; } } ans=(ans+dp[0][j][k][1]*hd[0][j][k]+dp[1][j][k][1]*hd[1][j][k])%p; //printf("able hd: %lld %lld\n", hd[0][j][k], hd[1][j][k]); //printf("add hd: %lld %lld\n", dp[0][j][k][1]*hd[0][j][k], dp[1][j][k][1]*hd[1][j][k]); ans=(ans+tail[0][j][k]*hd[0][j][k]+tail[1][j][k]*hd[1][j][k])%p; } ans=(ans+dp[0][j][m][1]+dp[1][j][m][1])%p; //printf("add: %lld %lld\n", dp[0][j][m][1], dp[1][j][m][1]); } return ans; } } signed main() { scanf("%s%s%s", mp[1]+1, mp[2]+1, s+1); n=strlen(mp[1]+1); m=strlen(s+1); //force::solve(); ll ans=task::solve(1); //cout<<"first iterator: "<<ans<<endl; reverse(mp[1]+1, mp[1]+n+1); reverse(mp[2]+1, mp[2]+n+1); printf("%lld\n", (ans+(m!=1?task::solve(0):0))%p); return 0; }