题目：
十分巧妙的dp。
关键是思考式子的意义，就能根据意义来推。
本题a[i]^2的意义可以看做是有两个人在排序列，排出来的结果一样的方案。（思路在于“方案 * 方案”的乘法原理）
这是10s+的代码：
#include#include #include #define ll long longusing namespace std;const int N=505;const ll mod=1024523;int n,m;char a[N],b[N];ll dp[2][N][N];int main(){ scanf("%d%d ",&n,&m); cin>>(a+1)>>(b+1); dp[0][0][0]=1; for(int i=1;i<=n+m;i++) { memset(dp[i&1],0,sizeof dp[i&1]); for(int j=max(0,i-m);j<=n&&j<=i;j++) for(int k=max(0,i-m);k<=n&&k<=i;k++) { if(b[m-(i-j)+1]==b[m-(i-k)+1])(dp[i&1][j][k]+=dp[(i-1)&1][j][k])%=mod; if(j&&a[n-j+1]==b[m-(i-k)+1])(dp[i&1][j][k]+=dp[(i-1)&1][j-1][k])%=mod; if(k&&b[m-(i-j)+1]==a[n-k+1])(dp[i&1][j][k]+=dp[(i-1)&1][j][k-1])%=mod; if(j&&k&&a[n-j+1]==a[n-k+1])(dp[i&1][j][k]+=dp[(i-1)&1][j-1][k-1])%=mod;// printf("dp[%d][%d][%d]=%lld\n",i,j,k,dp[i&1][j][k]); } } printf("%lld",dp[(n+m)&1][n][n]); return 0;}
如果把字符串一开始就翻转，可以变成9s+；把 ( i & 1 ) 和 ( i - j )之类的设个变量代替，可以变成7s+；
把long long改成int，可以变成4s+！
#include#include #include #define ll long longusing namespace std;const int N=505,mod=1024523;int n,m;char a[N],b[N];int dp[2][N][N];int main(){ scanf("%d%d ",&n,&m); cin>>(a+1)>>(b+1); for(int i=1;i<=(n>>1);i++)swap(a[i],a[n-i+1]); for(int i=1;i<=(m>>1);i++)swap(b[i],b[m-i+1]); dp[0][0][0]=1; for(int i=1;i<=n+m;i++) for(int j=max(0,i-m);j<=n&&j<=i;j++) for(int k=max(0,i-m);k<=n&&k<=i;k++) { int x=(i&1),y=!x,u=i-j,v=i-k; dp[x][j][k]=0; if(b[u]==b[v])(dp[x][j][k]+=dp[y][j][k])%=mod; if(j&&a[j]==b[v])(dp[x][j][k]+=dp[y][j-1][k])%=mod; if(k&&b[u]==a[k])(dp[x][j][k]+=dp[y][j][k-1])%=mod; if(j&&k&&a[j]==a[k])(dp[x][j][k]+=dp[y][j-1][k-1])%=mod;// printf("dp[%d][%d][%d]=%lld\n",i,j,k,dp[i&1][j][k]); } printf("%d",dp[(n+m)&1][n][n]); return 0;}