既见君子

同济医学生的起落落落落人生记录

[BZOJ1444][Jsoi2009]有趣的游戏

tag:AC自动机上概率dp+高斯消元

上次考试的时候没有写出来表示不开心,现在终于A了道差不多的题了呢旋转起来~

这道题也是把AC自动机建出来把儿子补全,然后对于每一个要赢v的人做一次高消.

f[i]表示站在i号节点v这个人的胜率,f[i]=sigma(p[j]*f[son]),根据这个式子,发现是带环的,就高消啦.

有趣的一点是题目给出的条件恰好避免了要去掉fail树的子树的情况,所以每一个end只会有一个位置,就很方便.

//看起来也是蛮裸的然而我调了好久QwQ

//网上的题解为什么都是迭代的做法?这个高消不是更方便么ovo

时间复杂度O(n^(n^2)^3)=O(10^7)

Code:http://paste.ubuntu.net/15391149/


评论
©既见君子
Powered by LOFTER