luogu P6125 [JSOI2009]有趣的游戏
2021-04-08 08:24
标签：高斯 com 字符串长度 题解 为什么 定义 problem ref 怎么 LINK：有趣的游戏 直接说做法了。首先是 题目中说了每个字符串长度相同 而我一直在思考AC自动机可能存在一些节点是不合法的且其还是其他节点的fail节点这个时候我很茫然不知道怎么dp了。。 实际上 长度相同那么一定不存在上述情况 发生 那么久很好解决了 我们很容易就可以列出来概率矩阵。 显然是存在一些环的问题的 对于终止节点我们定义其不向其他节点做出概率贡献。 然后我们利用这个矩阵不断的自乘进行概率的转移 最后会不断收敛 最后就是第一行的值了 (至于为什么 自己思考。 当然我们也应该知道这个应该是收敛的 因为可以考虑两种情况 多种概率不断交换的 但是其值不变的 乘多少次都无效。 对于概率改变的 我们自乘矩阵几十次也相当于一个矩阵被我们乘了2^几十次 这个是非常庞大的所以该转移的概率显然也转移完了 我们把后面的精度忽略掉就是正确答案。 当然这个思路并不是那么顺畅 比较顺的是 高斯消元啊 遇到有环的问题 首选高消且这个数据范围还支持高消。 设f[i]表示到达第i个点的期望次数 列出来i的转移方程。 可以发现 f[0]=1+... 因为初始是1 我们将这n个方程组解一下即可得到到达每个点的期望次数。同时注意终止节点始终不贡献转移。 可以发现最后求的是概率 感性的理解 这里的期望次数其实就是概率 可以这样考虑 我们初始只有f[0]=1 这个表示了0被期望经过的次数。 除了0这个节点 其余的所有节点都是从0出发来经过的 0到他们的期望次数显然
综上这道题两种方法均可。 luogu P6125 [JSOI2009]有趣的游戏 标签：高斯 com 字符串长度 题解 为什么 定义 problem ref 怎么 原文地址：https://www.cnblogs.com/chdy/p/12464619.html我是不会告诉你我看完题后不太会 摸了2h鱼后看题解 一直翻发现自己题目有些没读完整。。
上一篇：简明讲解一致性哈希算法
下一篇：Netty总结
文章标题：luogu P6125 [JSOI2009]有趣的游戏
文章链接：http://soscw.com/index.php/essay/72775.html