方案数的平方可以看做是两个人分别操作,操作到同一种结果的方案数。
直接 dp 一下即可。
代码如下:
#include <iostream>
#include <cstdio>
using namespace std;
const int S=505,p=1024523;
int n,m;
int a[S],b[S];
int dp[2][S][S];
inline void add(int &x,int y)
{
x+=y;
if(x>=p) x-=p;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf(" %c",&a[i]),a[i]-='A';
for(int i=1;i<=m;i++) scanf(" %c",&b[i]),b[i]-='A';
for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
for(int i=1;i<=m/2;i++) swap(b[i],b[m-i+1]);
dp[0][0][0]=1;
for(int i=0;i<=n+m;i++)
{
int u=i&1,v=i&1^1;
for(int j=0;j<=i-1&&j<=n;j++) for(int k=0;k<=i-1&&k<=n;k++) dp[v][j][k]=0;
for(int j=0;j<=i&&j<=n;j++)
{
for(int k=0;k<=i&&k<=n;k++)
{
if(dp[u][j][k]==0) continue;
int jb=i-j,kb=i-k;
if(j<n&&k<n&&a[j+1]==a[k+1]) add(dp[v][j+1][k+1],dp[u][j][k]);
if(jb<m&&k<n&&b[jb+1]==a[k+1]) add(dp[v][j][k+1],dp[u][j][k]);
if(j<n&&kb<m&&a[j+1]==b[kb+1]) add(dp[v][j+1][k],dp[u][j][k]);
if(jb<m&&kb<m&&b[jb+1]==b[kb+1]) add(dp[v][j][k],dp[u][j][k]);
}
}
}
printf("%d\n",dp[n+m&1][n][n]);
return 0;
}