题意：
中文题意，略。。。
思路：
第一问，求最长公子序列，模板题。。。
第二问，求最长公共子序列的个数，这个就比较有意思了。
设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 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 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 else 41 { 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 %d ",a[n%2][m],(b[n%2][m]+mod) % mod); 56 } 57 58 return 0; 59 }