传送门 两次取的序列一样,可以看成两个人分别玩一次,然后两个人得到的序列一样. 那这个题就变成了两个人各玩一次,求第一个人每次得到的序列在第二个人得到的序列中出现的次数和. 设f[i][j][k]表示第一个人上面用J颗，第二个人上面用k颗，产生序列相同的方案数。 手玩DP方程一发 然后就水过了。
#include<cstdlib> #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int f[505][505][505],n,m; char a[505],b[505]; int main(){ scanf("%d%d",&n,&m); scanf("%s%s",a+1,b+1); reverse(a+1,a+n+1); reverse(b+1,b+m+1); f[0][0][0]=1; for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) for (int k=0;k<=n;k++){ int t=i+j-k; if (t<0||t>m||f[i][j][k]==0) continue; if (a[i+1]==a[k+1]) f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%1024523; if (a[i+1]==b[t+1]) f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%1024523; if (b[j+1]==a[k+1]) f[i][j+1][k+1]=(f[i][j+1][k+1]+f[i][j][k])%1024523; if (b[j+1]==b[t+1]) f[i][j+1][k]=(f[i][j+1][k]+f[i][j][k])%1024523; } printf("%d",f[n][m][n]); }