【bzoj4043】【Cerc2014】【Vocabulary】【dp+预处理】-白红宇的个人博客

【bzoj4043】【Cerc2014】【Vocabulary】【dp+预处理】

发布日期：2021-11-16 15:38:22 浏览次数：7 分类：技术文章

本文共 1197 字，大约阅读时间需要 3 分钟。

Description

给你三个字符串，这些字符串有些单词模糊不可认了，用"?"来代表。

现在你可以用任意英文小写字母来代表它们。要求是使得给定的三个字符串中

所有的"?"被你认定的字母代替后，各不相同且按字典序出现。问有多少种方式。

Input

先给出一个数字N，代表数据组数。

接下来3*N行，每行给出一个字符串。长度<=1000 000

Output

输出结果 Mod 10^9+9

Sample Input

3
?heoret?cal
c?mputer
?cience
jagiellonia
?niversity
kra?ow
?
b
c

Sample Output

42562
52
1

题解：

首先我们把所有串变成一样长,不足的位置补'a'-1即可。

设f[i][0]表示对于前i个字符,三个串字典序相等的方案数。

f[i][1]表示对于前i个字符,前两个串的字典序相等并且小于第三个串的方案数。

f[i][2]表示对于前i个字符,后两个串的字典序相等并且大于第一个串的方案数。

f[i][3]表示对于前i个字符,三个串字典序各不相同并且从小到大排序的方案数。

这样转移显然非常麻烦。

我们考虑预处理。

设g[i][j][x][y][z]表示上一个状态是i,当前三个串的字符分别是x,y,z,转移到状态j的方案数。

这个东西暴力枚举所有情况即可。

然后f数组就很好求了。

代码：

#include
    
     #include
     
      #include
      
       #define N 1000010 #define P 1000000009using namespace std;int T,n,len,a[N],b[N],c[N],n1,n2,n3;long long g[4][4][28][28][28],f[N][4];char s1[N],s2[N],s3[N]; void pre(){  int i,j,k,l1,r1,l2,r2,l3,r3,x,y,z;  for (i=0;i<=27;i++)   for (j=0;j<=27;j++)    for (k=0;k<=27;k++){     if (i==27){l1=1;r1=26;}else{l1=i;r1=i;}	  for (x=l1;x<=r1;x++){	   if (j==27){l2=1;r2=26;}else{l2=j;r2=j;}	   for (y=l2;y<=r2;y++){	    if (k==27){l3=1;r3=26;}else{l3=k;r3=k;}	    for (int z=l3;z<=r3;z++){	      if (x==y&&y==z) g[0][0][i][j][k]++;	      if (x==y&&y

转载地址：https://blog.csdn.net/sunshinezff/article/details/50990173 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【bzoj2132】【圈地计划】【最小割】

下一篇：【bzoj2816】【ZJOI2012】【网络】【lct】

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！