[BZOJ2553][BEIJING2011]禁忌(AC自动机,概率动态规划,矩阵快速幂)

发布于 2018-03-24  113 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2553][BEIJING2011]禁忌(AC自动机,概率动态规划,矩阵快速幂)

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使用对方的每一个魔法的概率是均等的,那么每一次随机使用魔法所受到的禁忌伤害的期望值是多少。

Tag

AC自动机,概率动态规划,矩阵快速幂

解决思路

首先,如果一个串包含了其它的串,那么这个串的分割方式一定不会更优,所以先去掉这些包含了其它串的字符串。
然后怎么分割呢?其实就贪心地从头往后匹配,如果当前已经遇到一个完整的在字符集合中的字符串就权值 +1,然后重新开始匹配。由于我们已经去掉了包含关系,所以这样做是对的。
然后考虑如何转移。设 F[i][j] 表示生成到第 i 位,当前在 AC 自动机的第 j 位置,那么向它的每一个字符集内的儿子等概率转移,若儿子不是字符串集合末尾,则直接转移;否则,不向儿子转移转而向根节点 0 号转移,这意味着找到了一个匹配,所以要从头开始匹配,并且同时要把这个期望转移到答案中。
考虑到生成串的长度比较大而字符集大小和字符串总长都比较小,所以用矩阵快速幂优化转移。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2553][BEIJING2011]禁忌(AC自动机,概率动态规划,矩阵快速幂)


HNCJ OIer