目录
显示
题目链接
https://www.luogu.com.cn/problem/P1758
题解
转化问题:一种序列有 \(a_i\) 种产生方式,因此 \(\sum a_i^2\) 可以认为是两次产生同一序列的方案数。
设 \(f_{k,i,j}\) 表示两个人一共取了 \(k\) 个球,第一个人从上面取了 \(i\) 个球,第二个人从上面取 \(j\) 个球,产生同一序列的方案数。
转移时枚举两个人从上面或是从下面取,只有当取的球一样时才能转移。
时间复杂度 \(O(n^3)\)。
#include <iostream> #include <algorithm> #define MOD 1024523 using namespace std; int f[2][505][505]; char s[505],t[505]; int a[505],b[505]; int main() { int n,m; cin>>n>>m; cin>>(s+1); cin>>(t+1); for(int i=1;i<=n;i++) a[i]=(s[n-i+1]=='A'); for(int i=1;i<=m;i++) b[i]=(t[m-i+1]=='A'); f[0][0][0]=1; for(int k=1;k<=n+m;k++) { int p=k&1,q=p^1; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[p][i][j]=0; for(int i=max(k-m,0);i<=min(n,k);i++) for(int j=max(k-m,0);j<=min(n,k);j++) { if(i&&j&&a[i]==a[j]) f[p][i][j]=(f[p][i][j]+f[q][i-1][j-1])%MOD; if(i&&k-j&&a[i]==b[k-j]) f[p][i][j]=(f[p][i][j]+f[q][i-1][j])%MOD; if(j&&k-i&&a[j]==b[k-i]) f[p][i][j]=(f[p][i][j]+f[q][i][j-1])%MOD; if(k-j&&k-i&&b[k-j]==b[k-i]) f[p][i][j]=(f[p][i][j]+f[q][i][j])%MOD; } } cout<<f[(n+m)&1][n][n]<<endl; return 0; }