洛谷 P1654 OSU
定义
令$ S_i $表示$ 1..i $的分数(随机变量),$ L_i $表示从$ i $往前的连续$1$的长度(随机变量),$ a_i=0/1 $表示第$ i $位是否命中,$ p_i $表示第$ i $位命中的概率
分数的递推式
$$S_0=0$$
$$S_i=\begin{cases}
S_{i-1} & a_i==0,概率为1-p_i\\
S_{i-1}+3L_{i-1}^2+3L_{i-1}+1 & a_i==1,概率为p_i
\end{cases}$$
长度的递推式
$$L_0=0$$
$$L_i=\begin{cases} 0 & a_i==0,概率为1-p_i\\ L_{i-1}+1 & a_i==1,概率为p_i \end{cases}$$
$$L_i^2=\begin{cases} 0 & a_i==0,概率为1-p_i\\ L_{i-1}^2+2L_{i-1}+1 & a_i==1,概率为p_i \end{cases}$$
期望值的递推式(因为$ L_{i-1},L_{i-1}^2 $与$ a_i $无关,所以可以直接把上面两个式子的$ L_{i-1},L_{i-1}^2 $替换为$ E[L_{i-1}],E[L_{i-1}^2] $)
$$\begin{cases} E[L_0]=0\\ E[L_i]=p_i(E[L_{i-1}]+1) \end{cases}$$
$$\begin{cases} E[L_0^2]=0\\ E[L_i^2]=p_i(E[L_{i-1}^2]+2E[L_{i-1}]+1) \end{cases}$$
$$\begin{cases} E[S_0]=0\\ E[S_i]=E[S_{i-1}]+p_i(3E[L_{i-1}^2]+3E[L_{i-1}]+1) \end{cases}$$