普通统计LCS长度的n^2DP式，大家都会……
然后统计一下方案数
a[i]!=b[j]的时候，判一下f[i][j]和f[i-1][j],f[i][j-1]分别相不相等，如果相等就加上对应的方案数，再判和f[i-1][j-1]是否相等，相等就再减去[i-1][j-1]的方案数
a[i]==b[j]的时候，用[i-1][j-1]的方案数，然后如果f[i-1][j]或者[i][j-1]和f[i][j]相等的话，也加上对应的方案数
事实上还有一些比较傻逼的做法……用f[i][j]表示公共子序列的末尾必须在i位置和j位置的LCS长度，然后用树状数组找之前的f最大值，用最大值+1更新f，再查询之前f等于这个最大值的点的方案数的和，赋给这里的方案数……复杂度多个log，也可以过……
n^2:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 5010 #define MAXM 1010 #define INF 1000000000 #define MOD 100000000 #define eps 1e-8 #define ll long long #define lb(x) x&-x int f[2][MAXN],ct[2][MAXN]; char a[MAXN],b[MAXN]; int n,m; int main(){ int i,j; scanf("%s%s",a+1,b+1); n=strlen(a+1)-1; m=strlen(b+1)-1; for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(b[i]==a[j]){ f[i&1][j]=f[i&1^1][j-1]+1; ct[i&1][j]=(ct[i&1^1][j-1]+(f[i&1^1][j]==f[i&1][j])*ct[i&1^1][j]+(f[i&1][j-1]==f[i&1][j])*ct[i&1][j-1])%MOD; if(!f[i&1^1][j-1]){ ct[i&1][j]++; } }else{ f[i&1][j]=max(f[i&1^1][j],f[i&1][j-1]); ct[i&1][j]=(-(f[i&1^1][j-1]==f[i&1][j])*ct[i&1^1][j-1]+(f[i&1^1][j]==f[i&1][j])*ct[i&1^1][j]+(f[i&1][j-1]==f[i&1][j])*ct[i&1][j-1]+MOD)%MOD; } } } printf("%d\n%d\n",f[m&1][n],ct[m&1][n]); return 0; } /* AAAA. A. */ n^2 log n:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 5010 #define MAXM 1010 #define INF 1000000000 #define MOD 100000000 #define eps 1e-8 #define ll long long #define lb(x) x&-x int f[MAXN],ct[MAXN],c[MAXN][MAXN]; int C[MAXN]; char a[MAXN],b[MAXN]; int n,m; int ans,ans2; int ask(int x){ int re=0; for(;x;x-=lb(x)){ re=max(re,C[x]); } return re; } void change(int x,int y){ for(;x<=n;x+=lb(x)){ C[x]=max(C[x],y); } } int Ask(int *c,int x){ int re=0; for(;x;x-=lb(x)){ (re+=c[x])%=MOD;; } return re; } void Change(int *c,int x,int y){ for(;x<=n;x+=lb(x)){ (c[x]+=y)%=MOD; } } int main(){ int i,j; scanf("%s%s",a+1,b+1); n=strlen(a+1)-1; m=strlen(b+1)-1; for(i=1;i<=m;i++){ for(j=n;j;j--){ if(b[i]==a[j]){ int t=ask(j-1); f[j]=t+1; change(j,f[j]); if(f[j]==1){ ct[j]=1; }else{ ct[j]=Ask(c[t],j-1); } Change(c[f[j]],j,ct[j]); if(f[j]>ans){ ans=f[j]; ans2=0; } if(f[j]==ans){ (ans2+=ct[j])%=MOD; } } } } printf("%d\n%d\n",ans,ans2); return 0; } /* AAAA. A. */
