bzoj1444 有趣的游戏（AC自动机+概率dp）
2024-09-03 23:55:33
题意：
给定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*(nl)^3)
最新文章
- vsnprintf
- ASP.NET MVC 5 入门教程 (2) 控制器Controller
- ThinkPHP 源码分析之常量 IS_AJAX
- WC约束示使用
- Cookie的Domain
- 关于ligerui和其他前端脚本的学习方法（适用于自己）
- nginx 504 Gateway Time-out错误解决办法
- Unity 捕获IronPython脚本错误
- CKEditor不借助CKFinder实现图片上传（.net版 ashx实现）
- WPF 只允许打开一个实例
- MySQL-ISNULL()、IFNULL()和NULLIF()函数
- linux命令及用法
- html5 css选择器。 井号，句号的区别
- 使用token和redis怎样判断账户是否失效和异地登录
- （转）Spring Boot(十一)：Spring Boot 中 MongoDB 的使用
- POJ - 3984迷宫问题（最短路径输出）
- MySQL安装指南(转)
- 856. Score of Parentheses
- java指纹识别+谷歌图片识别技术_源代码
- 【MySql】【Navicat】下载，安装，激活攻略