2553: [BeiJing2011]禁忌
Time Limit: 20 Sec Memory Limit: 128 MBSec Special Judge
Submit: 595 Solved: 231
[Submit][Status][Discuss]
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，表示禁忌串。
Output
一个非负实数，表示所受到禁忌伤害的期望值。
Sample Input
aa
abb
Sample Output
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 205
struct node{long double p[MAXN][MAXN];node(){memset(p,,sizeof(p));}}a,ans;
int n,m,K,cnt,end[MAXN],q[MAXN],fail[MAXN],vis[MAXN],tr[MAXN*][];
char ch[MAXN];
inline int read()
{
int x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
inline node operator *(node &x,node &y)//定义矩阵乘运算
{
node z;
for(int i=;i<=cnt+;i++)
for(int j=;j<=cnt+;j++)
for(int k=;k<=cnt+;k++)
z.p[i][j]+=x.p[i][k]*y.p[k][j];
return z;
}
void insert()
{
int now=,len=strlen(ch+);
for(int i=;i<=len;i++)
{
if(!tr[now][ch[i]-'a']) tr[now][ch[i]-'a']=++cnt;
now=tr[now][ch[i]-'a'];
}
end[now]=;
}
void build()
{
int head=,tail=;
for(int i=;i<K;i++) if(tr[][i]) q[++tail]=tr[][i];
while(++head<=tail)
{
int x=q[head];
for(int i=;i<K;i++)
{
if(!tr[x][i]) tr[x][i]=tr[fail[x]][i];
else {fail[tr[x][i]]=tr[fail[x]][i]; q[++tail]=tr[x][i];}
}
}
}
void get()
{
int head=,tail=; long double chty=(long double)1.0/K;//期望常数
q[]=; vis[]=;
while(++head<=tail)
{
int x=q[head];
for(int i=;i<K;i++)
{
if(!vis[tr[x][i]]) vis[tr[x][i]]=,q[++tail]=tr[x][i];
if(end[tr[x][i]]) a.p[x][cnt+]+=chty,a.p[x][]+=chty;
else a.p[x][tr[x][i]]+=chty;
}
}
a.p[cnt+][cnt+]=;
}
int main()
{
//freopen("cin.in","r",stdin);
//freopen("cout.out","w",stdout);
n=read(); m=read(); K=read();
for(int i=;i<=n;i++) {scanf("%s",ch+); insert();}
build();
get();
for(int i=;i<=cnt+;i++) ans.p[i][i]=;
for(;m;m>>=,a=a*a) if(m&) ans=ans*a;
printf("%.7f\n",(double)ans.p[][cnt+]);
return ;
}