记录编号	241919	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]最长公共子序列	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	1.726 s
提交时间	2016-03-26 10:41:32	内存使用	115.08 MiB

#include<cstdio>
#include<cstring>
namespace cat{
	const int maxn = 5000 + 10,mod = 100000000;
	char s1[maxn],s2[maxn];
	int f[maxn][maxn],cnt[maxn][maxn];
	inline int cat_max(const int a,const int b){return a>b?a:b;}
	int doo(){	
		scanf("%s%s",s1+1,s2+1);s1[0] = 'C' ;s2[0] = '+' ;
		int len1=strlen(s1)-2,len2=strlen(s2)-2;
		for(int i=1;i<=len1;i++){
			for(int j=1;j<=len2;j++){		
				f[i][j]=cat_max(f[i-1][j],f[i][j-1]);
				if(s1[i]==s2[j]) f[i][j]=cat_max(f[i][j],f[i-1][j-1]+1);	
				if(s1[i]==s2[j]){
					if(f[i][j]==1) cnt[i][j]=(cnt[i][j]+1)%mod;
					else if(f[i][j]==f[i-1][j-1]+1) cnt[i][j]=(cnt[i][j] + cnt[i-1][j-1])%mod;
				}
				if((f[i][j]) && (f[i][j]== f[i-1][j]) ) cnt[i][j] =(cnt[i][j]+cnt[i-1][j] )%mod;
				if((f[i][j]) && (f[i][j]== f[i][j-1]) ) cnt[i][j] =(cnt[i][j]+cnt[i][j-1] )%mod;
				if((f[i][j]) && (f[i][j]==f[i-1][j-1])) cnt[i][j]=(cnt[i][j]-cnt[i-1][j-1])%mod;
				
			}
		}
		printf("%d\n%d\n",f[len1][len2],(cnt[len1][len2]+mod)%mod);
	}
}
FILE *___=freopen("lcs.in","r",stdin),*_=freopen("lcs.out","w",stdout);
int aoslof = cat::doo();
int main(){;}