Description
Solution
要求lcs的方案，那么很显然就是在lcs的数组上面去判断相同的方案。 我们知道求lcs的f[i][j]=1、s[i]=s[j]==>f[i-1][j-1]+1；2、max(f[i-1][j],f[i][j-1]) 那么现在我们就要考虑用到i和不用到i的情况的和（用到i即判断是用到s[i]=s[j]来转移） 我们设g[i][j]为A串前i个和B串前j个最长公共子序列为f[i][j]的方案数。 不用i：判断是否有f[i-1][j]转移过来（因为f[i][j-1]转移可能还是用到了i） 用i：在B串中找一个最近的s[i]位置为x，判断是否由f[i-1][x-1]转移过来
Code
using namespace std;
const int maxn=1007,mo=1e9+7;
typedef long long ll;
ll i,j,k,l,t,n,m,ans;
char s[maxn],st[maxn];
ll f[
maxn][
maxn],g[
maxn][
maxn];
ll b[
maxn][
27];
int main(){
// freopen("fan.in","r",stdin);
scanf("%s",s+1);n=strlen(s+1);
scanf("%s",st+1);m=strlen(st+1);
fo(i,1,m){
fo(j,0,25)b[i][j]=b[i-1][j];
b[i][st[i]-'a']=i;
}
fo(i,1,n){
fo(j,1,m){
if(s[i]==st[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j-1]));
}
}
fo(i,1,n)g[i][0]=1;
fo(i,0,m)g[0][i]=1;
fo(i,1,n){
fo(j,1,m){
if(f[i][j]==f[i-1][j])(g[i][j]+=g[i-1][j])%=mo;
l=b[j][s[i]-'a'];if(!l)continue;
if(f[i-1][l-1]+1==f[i][j])(g[i][j]+=g[i-1][l-1])%=mo;
}
}
printf("%lld\n",g[n][m]);
}
