记录编号	244477	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]最长公共子序列	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.697 s
提交时间	2016-04-01 10:15:49	内存使用	0.38 MiB

#include<cstdio>
#include<cstring>
const int maxn=5005;
char s1[maxn],s2[maxn];
int len[2][maxn],num[2][maxn];
int max(int a,int b){
	return a>b?a:b;
}
int main(){
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	scanf("%s %s",s1+1,s2+1);
	int len1=strlen(s1+1),len2=strlen(s2+1);
	for(int i=1;i<len1;++i){
		for(int j=1;j<len2;++j){
			num[i&1][j]=0;
			len[(i&1)][j]=max(len[(i+1)&1][j],len[i&1][j-1]);
			if(s1[i]==s2[j])len[i&1][j]=max(len[i&1][j],len[(i+1)&1][j-1]+1);
			
			if((len[i&1][j])&&len[i&1][j]==len[(i+1)&1][j])num[(i&1)][j]+=num[(i+1)&1][j];
			if((len[i&1][j])&&len[i&1][j]==len[i&1][j-1])num[i&1][j]+=num[i&1][j-1];
			if((len[i&1][j])&&len[i&1][j]==len[(i+1)&1][j-1])num[i&1][j]-=num[(i+1)&1][j-1];
			
			if(s1[i]==s2[j]){
				if(len[i&1][j]==1){
					num[i&1][j]+=1;
				}
				else if(len[i&1][j]==len[(i+1)&1][j-1]+1)num[i&1][j]+=num[(i+1)&1][j-1];
			}
			
			num[i&1][j]%=100000000;
		
		}
	}
	printf("%d\n%d\n",len[(len1+1)&1][len2-1],num[(len1+1)&1][len2-1]);
//	while(1);
	fclose(stdin);fclose(stdout);
	return 0;
}