记录编号	340735	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]最长公共子序列	最终得分	100
用户昵称	Zwoi_只会打表抄代码的蒟蒻	是否通过	通过
代码语言	C	运行时间	2.680 s
提交时间	2016-11-06 21:24:17	内存使用	0.38 MiB

#include <stdio.h>
#include <string.h>
#define M 100000000;
int max(int x,int y)
{
	if(x>y) return x;
	else return y;
}
int a[2][5010],maxn,p,k1,k2,k3,ii,d[2][5010];
int lb,lc,i,j;
char c[5010],b[5010];
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	scanf("%s",b+1);
	lb=strlen(b+1)-1;
	scanf("%s",c+1);
	lc=strlen(c+1)-1;
	for(i=0;i<=lc;i++)
		d[0][i]=1;
	d[1][0]=1;
	for(i=1;i<=lb;i++)
	{
		ii=i&1;
		for(j=1;j<=lc;j++)
		{
			k1=k2=k3=0;
			if(b[i]==c[j])
			{
				a[ii][j]=a[!ii][j-1]+1;
				d[ii][j]=d[!ii][j-1];  
				k1=1;
			}
			else 
			{
				a[ii][j]=max(a[!ii][j],a[ii][j-1]);
				if(a[ii][j]==a[!ii][j-1]) k1=-1;
			}
			if((a[ii][j]==a[!ii][j]))
				k2=1;
			if((a[ii][j]==a[ii][j-1]))
				k3=1;
			d[ii][j]=(k1*d[!ii][j-1]+k2*d[!ii][j]+k3*d[ii][j-1])%M;
		}
	}
	printf("%d\n%d",a[lb&1][lc],d[lb&1][lc]);
	return 0;
}