题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2423
题目大意：求两个字符串的最长公共子序列长度和最长公共子序列个数。
这道题的话，对于神犇来说，肯定是一眼看出状态转移方程的。而我这个蒟蒻，看了几篇博客之后才看懂。。。
第一问模板lcs，大家肯定都会，就是设f[i][j]为A串跑到第i位，B串跑到第j为时的最长公共子序列长度，然后就有：
f[i][j]=f[i-1][j-1]+1 (a[i]==b[j])
=max(f[i-1][j],f[i][j-1]) (a[i]!=b[j]) （原谅我不会编辑公式）
我就解释一下第二问的方程。先设g[i][j]为A串跑到第i位，B串跑到第j为时的最长公共子序列个数，方程就是这样：
g[i][j]=g[i-1][j-1]
+g[i-1][j] (f[i][j]==f[i-1][j])
+g[i][j-1] (f[i][j]==f[i][j-1])
(a[i]==b[j])
=g[i-1][j] (f[i][j]==f[i-1][j])
+g[i][j-1] (f[i][j]==f[i][j-1])
-g[i-1][j-1] (f[i][j]==f[i-1][j-1])
(a[i]!=b[j])
这里当a[i]和b[j]相同时，g[i-1][j],g[i-1][j-1],g[i][j-1]这三个的最长公共子序列不会重复，因为这里的g[i-1][j-1]实际上还要在末尾添加上a[i]（或b[j]），因此这些lcs全都是以a[i],b[j]结尾的，而g[i-1][j]不包含以a[i]结尾的lcs，g[i][j-1]不包含以b[j]结尾的lcs，因此这三类lcs不会重复，可以直接相加。
当a[i]与b[j]不同时，最后当f[i][j]==f[i-1][j-1]时要减去g[i-1][j-1]就是因为这时g[i-1][j-1]被分别包含在g[i-1][j]和g[i][j-1]中，算了两次，要把重复的减掉。
于是就可以愉快地AC这道题了。
还有，一定要用滚动数组，不然爆！空！间！
丑代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int mod=;
int f[][],g[][];
char a[],b[];
int main()
{
int i,j,n,m;
scanf("%s%s",a,b);
n=strlen(a)-; m=strlen(b)-;
for(i=;i<=m;i++)g[][i]=; g[][]=;
for(i=;i<=n;i++)
for(j=;j<=m;j++)
if(a[i-]==b[j-]){
f[i&][j]=f[i&^][j-]+;
g[i&][j]=(g[i&^][j-]+(f[i&^][j]==f[i&][j])*g[i&^][j]+(f[i&][j-]==f[i&][j])*g[i&][j-])%mod;
}
else{
if(f[i&^][j]>f[i&][j-])f[i&][j]=f[i&^][j];else f[i&][j]=f[i&][j-];
g[i&][j]=((f[i&^][j]==f[i&][j])*g[i&^][j]+(f[i&][j-]==f[i&][j])*g[i&][j-]-(f[i&][j]==f[i&^][j-])*g[i&^][j-]+mod)%mod;
}
printf("%d\n%d",f[n&][m],g[n&][m]);
}