题意：
中文题意，略。。。
思路：
第一问，求最长公子序列，模板题。。。
第二问，求最长公共子序列的个数，这个就比较有意思了。
设len[i][j]表示表示第一个串到i位置，第二个串到j位置时的长度。
设lcs[i][j]表示第一个串到i位置，第二个串到j位置时，lcs的个数。
当a[i] == b[j]:
那么最长公共子序列肯定是可以从i-1,j-1的位置继承来的，所以lcs[i][j] += lcs[i-1][j-1]；
当len[i][j-1] = len[i][j]，说明lcs也可以从i,j-1的位置继承来，那么lcs[i][j] += lcs[i][j-1]；
当len[i-1][j] = len[i][j]，同理。
当a[i] != b[j]时：
要么从i – 1,j的位置继承而来，要么从i,j-1的位置继承而来。
但是当len[i][j-1] = len[i-1][j]时，说明两个lcs均是从i-1,j-1的位置继承而来，那么以i-1,j-1结尾的lcs的个数就被加了两次，所以要减去一次。
然后这题限制空间，所以得用滚动数组优化。
代码：
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int N = 5005; 7 const int mod = 1e8; 8 9 char x[N],y[N];10 11 int a[2][N],b[2][N];12 13 int main()14 {15 while (scanf("%s%s",x+1,y+1) != EOF)16 {17 int n = strlen(x+1) - 1;18 int m = strlen(y+1) - 1;19 20 for (int i = 0;i <= m;i++) b[0][i] = 1;21 b[1][0] = 1;22 23 for (int i = 1;i <= n;i++)24 {25 for (int j = 1;j <= m;j++)26 {27 int c = i % 2,p = 1 - c;28 29 if (x[i] == y[j])30 {31 a[c][j] = a[p][j-1] + 1;32 33 int tmp = b[p][j-1] % mod;34 35 if (a[c][j] == a[c][j-1]) tmp = (tmp + b[c][j-1]) % mod;36 if (a[c][j] == a[p][j]) tmp = (tmp + b[p][j]) % mod;37 38 b[c][j] = tmp;39 }40 else41 {42 a[c][j] = max(a[p][j],a[c][j-1]);43 44 int tmp = 0;45 46 if (a[c][j] == a[p][j]) tmp = (tmp + b[p][j]) % mod;47 if (a[c][j] == a[c][j-1]) tmp = (tmp + b[c][j-1]) % mod;48 if (a[c][j] == a[p][j-1]) tmp = (tmp - b[p][j-1]) % mod;49 50 b[c][j] = tmp;51 }52 }53 }54 55 printf("%d\n%d\n",a[n%2][m],(b[n%2][m]+mod) % mod);56 }57 58 return 0;59 }