UVA11468 Substring --- AC自动机 + 概率DP
2024-08-24 22:36:27
UVA11468 Substring
题目描述：
给定一些子串T1...Tn
每次随机选择一个字符（概率会给出）
构造一个长为n的串S，求T1...Tn不是S的子串的概率
直接把T1...Tn建成AC自动机
把无法到达的节点打上标记
\(dp(i,j)\)表示长度为 i , 在 j 号节点的概率
初始\(dp(0,0) = 1\)
转移方程：\(dp(i,j)=\sum_{mark(trans(j,c))\: !=\: 1} dp(i,trans(j,c))*p(c)\)
但这样不方便转移，
考虑一个状态能转移到哪些状态来DP
最终结果为 \(\sum_{0 <= i <= ac.size} \; dp(i,n)\)
记得看题目数据范围（看错了长度范围，莫名调了1h）
最新文章
- Theano conv2d的border_mode
- MongoDB 2: 安装和使用
- 基于FlashPaper的文档播放器
- Asp.Net复习篇之Asp.Net生命周期与Asp.Net页的生命周期
- Laravel 5 基础（二）- 路由、控制器和视图简介
- 微软职位内部推荐-Senior NLP Scientist & Developer
- 关于 Unity 中 ModelImporter.optimizeGameObjects
- OpenGL ES2.0基础入门
- gcc与g++的区别与联系
- XtraBackup增量备份
- 算法与数据结构(六) 迪杰斯特拉算法的最短路径(Swift版)
- sed命令替换目录
- （转）决定系数R2
- kubernetes学习笔记之十三：基于calico的网络策略入门
- .NET MVC 后台接受base64的上传图片
- java多线程快速入门（十一）
- windows server 2008 R2 计划任务备份系统
- SoundChannel和soundTransform的关系
- Codeforces 954C Matrix Walk (思维)
- LVS之NAT模型、DR模型配置和持久连接