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）
随机推荐
-
C# 访问https 未能创建 SSL/TLS 安全通道
C# 访问https请求被中止: 未能创建 SSL/TLS 安全通道(Could not create SSL/TLS secure channel) 一般GetResponse可以直接访问https ...
-
Arduino开发常见错误
使用Ethernet时需要指定访问服务器的ip,我用的是本机做服务器.但是有一天重启了路由器,ip地址就变了!程序得跟着改! Arduino突然烧写不了程序:可能是正在运行的程序让arduino死机了 ...
-
第三百三十四天 how can I 坚持
I give up my dream that day,else,I coming on,the day my heart is die…… 那天,梦已碎,那天,心已死. 晚上看了个电影<奔爱& ...
-
软件版本中的Alpha,Beta,RC,Trial是什么意思？
版本号: V(Version):即版本,通常用数字表示版本号.(如:EVEREST Ultimate v4.20.1188 Beta ) Build:用数字或日期标示版本号的一种方式.(如:VeryC ...
-
WCF与Web API 区别
WCF与Web API 区别(应用场景) Web api 主要功能: 支持基于Http verb (GET, POST, PUT, DELETE)的CRUD (create, retrieve, ...
-
hdu 3074 Multiply game（模板级线段树）
离机房关门还有十分钟,这点时间能干些什么?故作沉思地仰望星空,重新捋一下一天的学习进度,或者,砍掉一棵模板级线段树. 纯模板,就是把单点更新,区间求和改为单点更新,区间求积. 1A. #include ...
-
ZOJ3541 The Last Puzzle
这道题是宁波集训的那道题,讲课时轻描淡写吧(应该是我听课不认真罢了),所以这样就要靠自己的理解了, dp[i][j][0]表示从左端点开始完成整个区间的最小花费dp[i][j][1]表示从右端点开始完 ...
-
SSD固态硬盘测试工具收集（持续更新）
https://www.crsky.com/zhuanti/gutaiyingpanceshi.html https://www.crsky.com/zhuanti/ssdjiance.html ht ...
-
LuoguP1072 Hankson的趣味题
题目 原题链接 题解 题意即为 \[ gcd(x,a0)=a1 \\ lcm(x,b0)=b1 \\ 求x个数 \] 根据\(lcm\)的求解方式\(lcm(a,b)=a*b/gcd(a,b)\)可以 ...
-
林纳斯&#183;托瓦兹和Linux行为准则：揭穿7个谬论
欢迎访问网易云社区,了解更多网易技术产品运营经验. 作者:史蒂芬·沃恩·尼古斯(Steven J.Vaughan-Nichols),从事Linux开源工作 时间:格林威治标准时间2018年9月25日— ...