中国风html5网站模板,同安网站建设,利用公共dns做网站解析,品牌厂家网站建设题目大意 给定一个由且仅由字符H#xff0c;T构成的字符串\(S\)。 给定一个最初为空的字符串\(T\) #xff0c;每次随机地在\(T\)的末尾添加H或者T。 问当\(S\)为\(T\)的后缀时#xff0c;在末尾添加字符的期望次数。 对\({10}^97\)取模 题解 设\(f_i\)为从\(i-1\)匹配…题目大意 给定一个由且仅由字符HT构成的字符串\(S\)。 给定一个最初为空的字符串\(T\) 每次随机地在\(T\)的末尾添加H或者T。 问当\(S\)为\(T\)的后缀时在末尾添加字符的期望次数。 对\({10}^97\)取模 题解 设\(f_i\)为从\(i-1\)匹配到\(i\)期望的匹配次数\(g_i\)表示匹配到\(i\)后下一次失配能匹配到什么位置用KMP求\(s_i\sum_{j1}^if_j\) 考虑匹配到第\(i\)位的情况\[ f_i\frac12\times 1\frac12(1f_{g_{i-1}1}f_{g_{i-1}2}\cdots f_{i})\\ f_i2s_{i-1}-s_{g_{i-1}} \] 答案为\(s_n\) 时间复杂度\(O(n)\) 代码 转载于:https://www.cnblogs.com/ywwyww/p/8511045.html
