看到数据范围，显然 $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
     
      #include
      
       #include
       
        #include
        
         #include
         
          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\n%d\n",g[cur][m],f[cur][m]);    return 0;}