[BZOJ1444][JSOI2009]有趣的游戏(AC自动机,概率动态规划,矩阵快速幂)

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


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

本文链接地址:[BZOJ1444][JSOI2009]有趣的游戏(AC自动机,概率动态规划,矩阵快速幂)

Description

[BZOJ1444][JSOI2009]有趣的游戏(AC自动机,概率动态规划,矩阵快速幂)

Tag

AC自动机,矩阵快速幂

解决思路

把每一个人获胜的字符串构建出AC自动机。
设 F[i][j] 表示第 i 轮,当前在 AC 自动机的 j 号点的概率,那么按照对应概率向儿子分别转移。注意,当已经到达某一个任的字母序列尾时,此时标志某一个人胜利,那么就每一次只向自己转移。
转移多少次呢?很多很多次,只要精度小于两位即可。为了多次转移,可以矩阵快速幂优化,这样就不会有精度问题了。

代码

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

本文链接地址:[BZOJ1444][JSOI2009]有趣的游戏(AC自动机,概率动态规划,矩阵快速幂)


HNCJ OIer