CH 白色情人节2(⑤我心永恒-字符串序列个数统计)

背景

You’re here, there’s nothing I fear,
and I know that my heart will go on.
We’ll stay forever this way.
You are safe in my heart.
And my heart will go on and on.

描述

男主想要用三句话表达对女主的爱,男主要对这三句话进行一番锤炼,现在要找出三句话中永恒不变的事物,需要做的,就是计算出三份序列的最长公共子序列长度、公共子序列个数,其中个数对第201314个质数(2769433)取模。字符之间的匹配不区分大小写(即”a”与”A”视为相等)

输入格式

共三行,一行一个字母序列。

输出格式

第一行,三份序列的最长公共子序列长度。
第二行,三份序列的公共子序列个数对第201314个质数(2769433)取模得到的答案

样例输入

INeedYou
IMissYou
ILoveYou

样例输出

4
15

数据范围与约定

对于100%的数据,序列仅含大小写字母,序列长度均\leq 100

样例解释

最长公共子序列是IYou,长度为4,公共子序列分别是I Y o u IY Io Iu Yo Yu ou IYo IYu Iou You IYou,共4+6+4+1 = 15个

来源

本题有个无节操版本……

这题是统计公共子序列个数+去重

正解用了容斥原理,并且允许空串。

F[I][J][K]=2F[I-1][J-1][K-1]-F[I’-1][J’-1][K’-1] I’,J’,K’为I,J,K,之前出现a[i],b[j],c[k]的位置(没有就不用减)

 假设之前已经去重,那么F[I][J][K]只需与F[I’-1][J’-1][K’-1]去重。


#include<cstdio>

include<cstring>

include<cstdlib>

include<cmath>

include<functional>

include<algorithm>

include<cctype>

using namespace std;

define F (2769433)

define MAXN (100+10)

define For(i,n) for(int i=1;i<=n;i++)

define Rep(i,n) for(int i=0;i<=n;i++)

int len1,len2,len3,f[MAXN][MAXN][MAXN],pre1[MAXN],pre2[MAXN],pre3[MAXN],s[500]; char a[MAXN],b[MAXN],c[MAXN]; void make_pre(char a,int n,int pre) { memset(s,128,sizeof(s)); memset(pre,0,sizeof(pre)); For(i,n) { a[i]=tolower(a[i]); pre[i]=s[a[i]]; s[a[i]]=i; } } int main() { memset(f,0,sizeof(f)); scanf("%s%s%s",a+1,b+1,c+1);a[0]=b[0]=c[0]=' '; len1=strlen(a)-1,len2=strlen(b)-1,len3=strlen(c)-1; make_pre(a,len1,pre1); make_pre(b,len2,pre2); make_pre(c,len3,pre3); int cnt=0; For(i,len1) For(j,len2) For(k,len3) if (a[i]==b[j]&&b[j]==c[k]) f[i][j][k]=f[i-1][j-1][k-1]+1; else f[i][j][k]=max(max(f[i-1][j][k],f[i][j-1][k]),f[i][j][k-1]); cnt=f[len1][len2][len3]; // memset(f,0,sizeof(f)); Rep(i,len1) Rep(j,len2) Rep(k,len3) f[i][j][k]=1; For(i,len1) For(j,len2) For(k,len3) { f[i][j][k]=0; if (a[i]==b[j]&&b[j]==c[k]) { f[i][j][k]=(10F+f[i-1][j-1][k-1]2)%F; if (pre1[i]>0&&pre2[j]>0&&pre3[k]>0) f[i][j][k]=(F+f[i][j][k]-f[pre1[i]-1][pre2[j]-1][pre3[k]-1])%F; // if (!pre1[i]||!pre2[j]||!pre3[k]) f[i][j][k]--;
} else { f[i][j][k]=(10*F+f[i-1][j][k]+f[i][j-1][k]+f[i][j][k-1]-f[i-1][j-1][k]-f[i][j-1][k-1]-f[i-1][j][k-1]+f[i-1][j-1][k-1])%F; } }

printf(&quot;%d\n%d\n&quot;,cnt,(F+f[len1][len2][len3]-1)%F);
return 0;

}