1 条题解
-
2
社论 - P1152 CTSC 2006 歌唱王国
本文同步发表于洛谷博客。
对于随机变量 ,定义其「概率生成函数」(下文称为 )为形式幂级数 ,其中 表示条件 的概率。
易知它有这些简单性质:
- ,对所有可能出现的情况的概率求和;
- $F_X'(1) = \sum\limits_{i = 1} ^ \infty iP(X = i) = E(X)$,其中 表示随机变量 的值的数学期望。
设随机变量 表示随机恰好 个字符后,歌唱结束。
设 $F(x) = \sum\limits_{i = 1} ^ \infty P(X = i)x^i, G(x) = \sum\limits_{i = 0} ^ \infty P(X > i)x^i$,即随机恰好 个数后歌唱结束/不结束的 ,那么易知 的系数就是 系数的后缀和,于是现在既可以考虑它们表示的意义,也可以直接从这两个式子本身出发,得到下面这个式子,这里采用的是后者:
考虑 的系数后缀和又等于 系数整体向右偏移一位,然后再在最前面加上 所有系数的和,即 。
再进行简单的变换就得到了
$$F(x) = (x - 1)G(x) + 1\\ F'(x) = G(x) + (x - 1)G'(x)\\ E(X) = F'(1) = G(1)$$考虑在一个没有结束的序列上接下来强行接上 使其结束,有:
$$\left(\dfrac{x}{n}\right)^{|S|}G(x) = \sum_{i = 1} ^ {|S|}\left[pre_i = suf_i\right]\left(\dfrac{x}{n}\right)^{|S| - i}F(x) $$其中 表示字符串 存在长为 的公共前后缀。
最后把 代入简单变形即得
$$\dfrac{1}{n^{|S|}}E(X) = \sum_{i = 1} ^ {|S|}[pre_i = suf_i]\dfrac{1}{n^{|S| - i}}\\ E(X) = \sum_{i = 1} ^ {|S|}[pre_i = suf_i]n^i$$
- 1
信息
- ID
- 1152
- 时间
- 3000ms
- 内存
- 162MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 19
- 已通过
- 13
- 上传者