背景
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%的數據，序列僅含大小寫字母，序列長度均。
樣例解釋
最長公共子序列是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]去重。
[cpp] #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]=(10*F+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("%d\n%d\n",cnt,(F+f[len1][len2][len3]-1)%F);
return 0;
}
