看到数据范围，显然 $n^2$ 的 $dp$...
设 $f[i][j]$ 表示 $A$ 串考虑了前 $i$ 位，$B$ 串考虑了前 $j$ 位，最优情况下的方案数
但是好像没法判断转移来的是否为最优方案？
所以再设 $g[i][j]$ 表示 $A$ 串考虑了前 $i$ 位，$B$ 串考虑了前 $j$ 位，最优情况下的匹配数
那么对于 $g$ 有转移，$g[i][j]=max(g[i-1][j],g[i][j-1])$，如果 $A[i]==B[j]$，那么 $g[i][j]=max(g[i][j],g[i-1][j-1]+1)$
然后考虑 $f$ 的转移
如果 $g[i-1][j]==g[i][j]$ 则 $f[i][j]+=f[i-1][j]$，如果 $g[i][j-1]==g[i][j]$ 则 $f[i][j]+=f[i][j-1]$，如果 $A[i]==B[j]$ 并且 $g[i][j]==g[i-1][j-1]$ 那么 $f[i][j]+=g[i-1][j-1]$
发现输出比答案大...
仔细分析发现如果 $g[i-1][j-1]==g[i][j]$，那么 $f[i-1][j-1]$ 的贡献会分别通过 $f[i][j-1],f[i-1][j]$ 转移到 $f[i][j]$ ，就被算了两次
所以如果 $g[i-1][j-1]==g[i][j]$ ，$f[i][j]$ 还要再减去 $f[i-1][j-1]$
最后，一定要滚动数组
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=5007,mo=1e8; inline int fk(int x) { return x>=mo ? x-mo : x; } int n,m,f[2][N],g[2][N]; char a[N],b[N]; int main() { scanf("%s",a+1); scanf("%s",b+1); n=strlen(a+1)-1,m=strlen(b+1)-1; for(int i=0;i<=m;i++) f[0][i]=1; int cur=0,pre; for(int i=1;i<=n;i++) { pre=cur; cur^=1; f[cur][0]=1; for(int j=1;j<=m;j++) g[cur][j]=f[cur][j]=0; for(int j=1;j<=m;j++) { if(a[i]==b[j]) g[cur][j]=g[pre][j-1]+1,f[cur][j]=f[pre][j-1]; if(g[pre][j]>g[cur][j]) g[cur][j]=g[pre][j],f[cur][j]=f[pre][j]; else if(g[pre][j]==g[cur][j]) f[cur][j]=fk(f[cur][j]+f[pre][j]); if(g[cur][j-1]>g[cur][j]) g[cur][j]=g[cur][j-1],f[cur][j]=f[cur][j-1]; else if(g[cur][j-1]==g[cur][j]) f[cur][j]=fk(f[cur][j]+f[cur][j-1]); if(g[cur][j]==g[pre][j-1]) f[cur][j]=fk(f[cur][j]-f[pre][j-1]+mo); } } printf("%d %d ",g[cur][m],f[cur][m]); return 0; }