首页 > 代码库 > bzoj1444 有趣的游戏(AC自动机+概率dp)

bzoj1444 有趣的游戏(AC自动机+概率dp)

题意:

给定n个长度为l的模式串,现在要用前m个大写字母生成一个随机串,每个字符有自己的出现几率,第一次出现的字符串获胜,求最终每个字符串的获胜几率。

分析:

容易想到先把所有的字符串建成一个AC自动机

然后对于生成的随机串就相当于从AC自动机的root开始在自动机上走,然后求走到每个单词节点的概率

因为这是存在环的,不是DAG图,所以不能直接DP

考虑构造出刚开始的转移矩阵,然后对转移矩阵作矩阵乘法不断迭代就能得到正确答案了

转移矩阵如何建呢?

  1)a[i][ch[i][j]]+=p[j] (普通的转移,注意一定要累加,不能直接赋值

  2)若某个节点是danger节点,那么根据题意,它是说明已经提前走完了一个字符串,不能再走离这个位置,所以对于这种节点,只能a[i][i]=1.0,其他不要

时间复杂度O(K*(nm)^3)

bzoj1444 有趣的游戏(AC自动机+概率dp)