注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2553][BeiJing2011]禁忌  

2015-04-23 21:41:38|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2553: [BeiJing2011]禁忌

Time Limit: 20 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 306  Solved: 108
[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

第一行包含三个正整数Nlenalphabet

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

Output

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

Sample Input

2 4 2 aa abb

Sample Output

0.75 【样例1解释】 一共有2^4 = 16种不同的魔法。 需要注意的是“aabb”的禁忌伤害是1而不是2。

HINT

100%的数据中N ≤ 5len ≤1091 ≤ alphabet ≤ 26

在所有数据中,有不少于40%的数据中:N = 1

数据保证每个串Ti的长度不超过15,并且不是空串。

数据保证每个Ti均仅含有前alphabet个小写字母。

数据保证集合T中没有相同的元素,即对任意不同的ij,有TiTj

评分方法

对于每一组数据,如果没有得到正确的输出(TLEMLERTE、输出格式错误等)得0分。

否则:设你的输出是YourAns,标准输出是StdAns

MaxEPS = max(1.0 , StdAns)×10-6

如果|YourAns – StdAns| ≤ MaxEPS则得10分,否则得0分。

即:你的答案需要保证相对误差或绝对误差不超过10-6

Solution

考虑状态转移,是AC自动机变为Trie图进行概率转移,由于每次转移都是一样的,因此矩阵快速幂。
统计答案要额外开一个节点T,到这个节点的时候,把串分成两部分,一部分拿去贡献答案,另一部分接着跑dp,然后每次f[T]+=到T的概率,所以T要连自环

Code

/**************************************************************
    Problem: 2553
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:48 ms
    Memory:1352 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
typedef long double ld;
int n,a,i,j,k,ch[110][26],fail[110],danger[110],las,tot,l=1,r,q[11000];char s[110];
struct M{ld m[110][110];}f,t,c;ld tmp;double ans;
M operator*(const M&a,const M&b){
    memset(&c,0,sizeof(c));
    for(int i=0;i<=tot;i++)
    for(int k=0;k<=tot;k++)
    for(int j=0;j<=tot;j++)
    c.m[i][j]+=a.m[i][k]*b.m[k][j];
    return c;
}
int main(){
    scanf("%d%d%d",&n,&k,&a);k--;tmp=1.0/a;
    for(;n--;){
        scanf("%s",s);las=0;
        for(i=0;s[i];i++){
            s[i]-='a';
            if(!ch[las][s[i]])ch[las][s[i]]=++tot;
            las=ch[las][s[i]];
        }
        danger[las]=1;
    }
    for(i=0;i<a;i++)if(ch[0][i])q[++r]=ch[0][i];
    for(;l<=r;l++)
    for(i=0;i<a;i++)
    if(j=ch[q[l]][i]){
        fail[q[++r]=j]=ch[fail[q[l]]][i];
        danger[j]|=danger[fail[j]];
    }
    else ch[q[l]][i]=ch[fail[q[l]]][i];tot++;
    for(i=0;i<tot;i++)
    for(j=0;j<a;j++)if(!danger[ch[i][j]])t.m[i][ch[i][j]]+=tmp;
    else t.m[i][0]+=tmp,t.m[i][tot]+=tmp;
    for(t.m[tot][tot]=1,f=t;k;k>>=1,t=t*t)if(k&1)f=f*t;
    ans=f.m[0][tot];printf("%.10lf\n",ans);
}

  评论这张
 
阅读(199)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018