[BZOJ2553]禁忌

2553: [BeiJing2011]禁忌

Time Limit: 20 Sec Memory Limit: 128 MBSec Special Judge

Description

Magic Land上的人们总是提起那个传说：他们的祖先John在那个东方岛屿帮助Koishi与其姐姐Satori最终战平。而后，Koishi恢复了读心的能力……

如今，在John已经成为传说的时代，再次造访那座岛屿的人们却发现Koishi遇到了新麻烦。

这次她遇到了Flandre Scarlet——她拥有可以使用禁忌魔法而不会受到伤害的能力。

为了说明什么是禁忌魔法及其伤害，引入以下概念：

1．字母集A上的每个非空字符串对应了一个魔法。

其中A是包含了前alphabet个小写字母的集合。

2．有一个集合T，包含了N个字母集A上的字符串

T中的每一串称为一个禁忌串（Taboo string）

3．一个魔法，或等价地，其对应的串s因为包含禁忌而对使用者造成的伤害按以下方式确定：

把s分割成若干段，考虑其中是禁忌串的段的数目，不同的分割可能会有不同的数目，其最大值就是这个伤害。

由于拥有了读心的能力，Koishi总是随机地使用Flandre Scarlet的魔法，可以确定的是，她的魔法正好对应字母集A上所有长度为len的串。

但是，Flandre Scarlet所使用的一些魔法是带有禁忌的，由于其自身特性，她可以使用禁忌魔法而不受到伤害，而Koishi就不同了。可怜的Koishi每一次使用对方的魔法都面临着受到禁忌伤害的威胁。

你现在需要计算的是如果Koishi使用对方的每一个魔法的概率是均等的，那么每一次随机使用魔法所受到的禁忌伤害的期望值是多少。

Input

第一行包含三个正整数N、len、alphabet。

接下来N行，每行包含一个串T_i，表示禁忌串。

Output

一个非负实数，表示所受到禁忌伤害的期望值。

Sample Input

2 4 2
aa
abb

Sample Output

0.75

题解：

虽然已经打了一些概率，但是……字符串上的dp还真的是让人束手无策啊……

在zyf神犇的提示之下总算是做出来了……

首先，我们当然要给所有禁忌串建立trie树，然后我们来分析一下：

如果有2个串A和B，满足A是B的前缀，那么B不可能比A更优，因为A和B中间可能还有其他的串

因此，在插入的时候如果我们碰到一个单词节点，就直接跳出即可

接下来，我们来构建ac自动机的fail指针，而且必须是trie图

那么考虑对ac自动机上的节点，对于他的子节点：

1、子结点没被标记（即不是禁忌串的结尾），有1/alphabet的概率转移到这个子结点，即f[i+1][k]+=f[i][j]/alphabet；

2、子结点被标记，有1/alphabet的概率转移这个被标记的子节点，接着直接到根，并且累加答案+1。

这也说明了为什么是trie图：不用trie图可能会漏状态

由于统计答案很难，所以，我们设节点总数为cnt，设root编号为0，并且再开一个虚拟节点cnt+1，在经过这个点的时候累加答案

也就是说标记点->cnt+1->root

我们不难发现，上面这个式子，即f[i+1][k]+=f[i][j]/alphabet，是一个线性的递推式，因此可以用矩阵乘法优化，设矩阵为A[i][j]

当矩阵乘法在图上应用时，A[i][j]的m次方表示从i点走m步到达j点时的某个值（边权，步数……之类的）

那么在本题中，我们的答案就是A[0][cnt+1]

设k=1/alphabet

在我们初始化矩阵时候，如果有标记，那么走到根的概率加上k，伤害累加值加上k（概率是k，伤害是1）

如果没有标记，直接加上概率k/1

代码见下：

  1 #include<cstdio>
  2 #include<cstring>
  3 using namespace std;
  4 int n,len,size,cnt,hd=1,tl;
  5 char s[10][15];
  6 struct node
  7 {
  8     node *ch[26],*f;
  9     int id,mark;
 10     node(int v){memset(ch,0,sizeof(ch));id=v,mark=0;}
 11 }*root,*man[10010],*q[10100];
 12 struct Marx
 13 {
 14     long double m[160][160];
 15     void clear()
 16     {
 17         for(int i=0;i<160;i++)
 18             for(int j=0;j<160;j++)
 19                 m[i][j]=0;
 20     }
 21 }A,B,tmp;
 22 inline void insert(char *t)
 23 {
 24     node *rt=root;int m=strlen(t);
 25     for(int i=0;i<m;i++)
 26     {
 27         if(rt->mark)return;
 28         if(!rt->ch[t[i]-'a'])
 29         {
 30             rt->ch[t[i]-'a']=new node(++cnt);
 31             man[cnt]=rt->ch[t[i]-'a'];
 32         }
 33         rt=rt->ch[t[i]-'a'];
 34     }
 35     rt->mark=1;
 36 }
 37 inline void bfs()
 38 {
 39     root->f=NULL;q[++tl]=root;
 40     while(hd<=tl)
 41     {
 42         node *rt=q[hd++];
 43         for(int i=0;i<size;i++)
 44         {
 45             if(rt->ch[i])
 46             {
 47                 q[++tl]=rt->ch[i];
 48                 node *u=rt->f;
 49                 while(u&&!u->ch[i])u=u->f;
 50                 rt->ch[i]->f=(u)?u->ch[i]:root;
 51             }
 52             else
 53             {
 54                 node *u=rt->f;
 55                 rt->ch[i]=(u)?u->ch[i]:root->ch[i];
 56             }
 57         }
 58     }
 59 }
 60 inline void intn()
 61 {
 62     long double k=(long double)1/size;
 63     for(int i=0;i<=cnt;i++)
 64         if(!man[i]->mark)
 65             for(int j=0;j<size;j++)
 66                 if(man[i]->ch[j])
 67                     if(man[i]->ch[j]->mark)
 68                         A.m[i][cnt+1]+=k,A.m[i][0]+=k;
 69                     else
 70                         A.m[i][man[i]->ch[j]->id]+=k;
 71                 else
 72                     A.m[i][0]+=k;
 73     A.m[cnt+1][cnt+1]=1;
 74 }
 75 int main()
 76 {
 77     scanf("%d%d%d",&n,&len,&size);
 78     root=new node(0);
 79     man[0]=root;
 80     for(int i=1;i<=n;i++)
 81         scanf("%s",s[i]),insert(s[i]);
 82     bfs();intn();
 83     B.m[0][0]=1;
 84     while(len)
 85     {
 86         if(len&1)
 87         {
 88             tmp.clear();
 89             for(int k=0;k<=cnt+1;k++)
 90                 for(int j=0;j<=cnt+1;j++)
 91                     tmp.m[0][j]+=B.m[0][k]*A.m[k][j];
 92             for(int i=0;i<=cnt+1;i++)
 93                 for(int j=0;j<=cnt+1;j++)
 94                     B.m[i][j]=tmp.m[i][j];
 95         }
 96         len>>=1;    
 97         tmp.clear();
 98         for(int k=0;k<=cnt+1;k++)
 99             for(int i=0;i<=cnt+1;i++)
100                 for(int j=0;j<=cnt+1;j++)
101                     tmp.m[i][j]+=A.m[i][k]*A.m[k][j];
102         for(int i=0;i<=cnt+1;i++)
103             for(int j=0;j<=cnt+1;j++)
104                 A.m[i][j]=tmp.m[i][j];
105     }
106     double ans=B.m[0][cnt+1];
107     printf("%.9lf",ans);
108 }

BZOJ2553