记录编号	131500	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]最长公共子序列	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	1.681 s
提交时间	2014-10-24 16:24:54	内存使用	0.31 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
string s1,s2;
const int m=100000000;
int f[2][5001]={0},cnt[2][5001]={0};
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	cin>>s1;
	cin>>s2;
	int len1=s1.size()-1,n=s2.size()-1;
	for(int i=0;i<=n;i++) cnt[0][i]=1;
	int k;
	for(int i=1;i<=len1;i++)
	{
		k=i & 1;
		memset(f[k],0,sizeof(f[k]));
		memset(cnt[k],0,sizeof(cnt[k]));
		cnt[k][0]=1;
		cnt[!k][0]=1;
		for(int j=1;j<=n;j++)
		{
			if(s1[i-1]==s2[j-1]) 
			{
				f[k][j]=f[!k][j-1]+1;
				cnt[k][j]=cnt[!k][j-1];
				cnt[k][j]%=m;
				if(f[k][j]==f[!k][j])
				{
					cnt[k][j]+=cnt[!k][j];
					cnt[k][j]%=m;
				}
				if(f[k][j]==f[k][j-1])
				{
					cnt[k][j]+=cnt[k][j-1];
					cnt[k][j]%=m;
				}
			}
			else
			{
				if(f[k][j-1]>f[!k][j])
				{
					f[k][j]=f[k][j-1];
					cnt[k][j]+=cnt[k][j-1];
					cnt[k][j]%=m;
				}
				if(f[k][j-1]<f[!k][j])
				{
					f[k][j]=f[!k][j];
					cnt[k][j]+=cnt[!k][j];
					cnt[k][j]%=m;
				}
				if(f[k][j-1]==f[!k][j])
				{
					f[k][j]=f[!k][j];
					cnt[k][j]+=cnt[!k][j]+cnt[k][j-1]; 
					if(f[!k][j-1]==f[k][j]) cnt[k][j]-=cnt[!k][j-1];
					cnt[k][j]=(cnt[k][j]+3*m)%m;
				}
			}
		}
	}
	cout<<f[k][n]<<endl<<cnt[k][n];
	return 0;
}