求方案数，直接从 \(f[i-1][j]\) 和 \(f[i][j-1]\) 转移过来，如果 \(s1[i]==s2[j]\) 就加上 \(f[i-1][j-1]\) ，如果 \(s1[i]!=s2[j]\) 且 \(f[i][j]==f[i-1][j-1]\) 说明两边
转移到了 \(f[i-1][j-1]\) ，减去重复部分 \(f[i-1][j-1]\) 就行了。
比较好的理解方式是画个网格图，如果 \(s1[i]==s2[j]\) 就连条斜线边，第一问相当于是走斜线的次数最多从 \((1,1)\) 到 \((n,m)\) ，第二问相当于是算路径方案数，但
是两个路径不同当且仅当斜线经过不一样。
注意要滚动下数组和边界条件
#include<bits/stdc++.h>
#define il inline
#define maxn 5003
using namespace std;
typedef long long ll;
const ll mod=1e8;
il int read(){
char c;int f=0,x=0;
while(!isdigit(c=getchar()))f|=(c=='-');
while(isdigit(c))x=(x*10)+(c^48),c=getchar();
return f?-x:x;
}
char s1[maxn],s2[maxn];
int n,m,f[maxn][maxn];
ll f2[2][maxn];
int main(){
scanf("%s%s",(s1+1),(s2+1));
n=strlen(s1+1)-1,m=strlen(s2+1)-1;
f2[1][0]=1;
for(int i=0;i<=m;i++)f2[0][i]=1;
int p=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s1[i]!=s2[j])f[i][j]=max(f[i-1][j],f[i][j-1]);
else f[i][j]=max(f[i][j],f[i-1][j-1]+1);
int tmp=f[i][j];
if(f[i-1][j]==tmp)f2[p][j]=(f2[p][j]+f2[p^1][j])%mod;
if(f[i][j-1]==tmp)f2[p][j]=(f2[p][j]+f2[p][j-1])%mod;
if(s1[i]==s2[j])f2[p][j]=(f2[p][j]+f2[p^1][j-1])%mod;
if(s1[i]!=s2[j]&&f[i][j]==f[i-1][j-1])f2[p][j]=((f2[p][j]-f2[p^1][j-1])%mod+mod)%mod;
}
p^=1;
for(int j=1;j<=m;j++)f2[p][j]=0;
}
printf("%d\n%d\n",f[n][m],f2[p^1][m]);
return 0;
}