题面：
有一个初始为空的序列，在序列末尾随机添加1或2，有p的概率添加1，1 - p的概率添加2，如果序列末尾有连着的两个相同的数k，那么他们会合并成k + 1，这个合并只要可行，可以一直持续下去
序列有个长度限制n，当序列凑到n位且无法合并，添加操作就结束，问结束时所有权值的和的期望。
solution:
假设数字i出现的概率为p(i)，则数字i + 1出现的期望可以粗略地估计为p(i)^2，那么，值大于50的数出现的概率就非常小了，对答案的贡献可以忽略不计
定义a[i][j]:在长度限制为i的情况下，最左端出现过数字j，最后让序列长度停止在i的概率
那么有a[i][j] = a[i][j - 1] * a[i - 1][j - 1]，即先出现一次j - 1，再出现j - 1的概率
类似地，定义b[i][j]，但加一个约束，序列初始时的第一个数字必须是2，有b[i][j] = b[i][j - 1] * a[i - 1][j - 1]
边界为a[i][1] = p，a[i][2] = b[i][2] = 1 - p
定义f[i][j]:构造一个长度为i的序列，构造结束时序列最左端为j，序列的和的期望
一般地，有f[i][j] = j + ∑(f[i - 1][k] * a[i - 1][k] * (1 - a[i - 2][k])) / ∑(a[i - 1][k] * (1 - a[i - 2][k])) (k = 1 ~ j - 1)
因为第一位确定为j时，第二位出现过的数字一定不能大于等于j，否则会和这个j合并
对于第三位，因为第二位的值已经确定，所以只需保证第三位不为k即可，乘上概率转移一下
特别地，当j = 1，
f[i][1] = 1 + ∑(f[i - 1][k] * b[i - 1][k] * (1 - a[i - 2][k])) / ∑(b[i - 1][k] * (1 - a[i - 2][k])) (k = 2 ~ 50)
最后统计答案为Ans = ∑f[n][i] * a[n][i] * (1 - a[n][i])
注意到转移超过五十次时，a，b数组的值就不在更新了
所以暴力前50次转移，后面的转移就可以用矩阵乘法了
#include
#include
#include
#include
#include
#include
#include
#include
#include
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
