[Codeforces908D]New Year and Arbitrary Arrangement(动态规划)

发布于 2018-04-07  167 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[Codeforces908D]New Year and Arbitrary Arrangement(动态规划)

Description

You are given three integers k, pa and pb.

You will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With probability pa / (pa + pb), add 'a' to the end of the sequence. Otherwise (with probability pb / (pa + pb)), add 'b' to the end of the sequence.

You stop once there are at least k subsequences that form 'ab'. Determine the expected number of times 'ab' is a subsequence in the resulting sequence. It can be shown that this can be represented by P / Q, where P and Q are coprime integers, and . Print the value of .

Tag

动态规划

题目大意

随机生成一个只包含a和b的串,a和b分别有不同的生成期望,求当生成至少K个子序列ab时停止,求期望的ab的子序列个数。

解决思路

设\(F[i][j]\)表示生成了i个ab的子序列,当前接了j个a时,达到终止状态还要加的个数的期望,那么有转移方程
\[F[i][j]=F[i][j+1]*pa+F[i+j][j]*pb\]
但要注意的是,这个式子的前一项是可以无限展开的,其实际意义就是可以无限地在后面加a而不加b,这样就永远达不到子序列ab出现k次的要求,所以当i+j>=K的时候不能这么转移。
而i+j>=K的时候,只要再加一个b就会停止,我们把式子化出来看看
\[F[i][j]=pb(i+j)+pa*pb(i+j+1)+pa^2*pb(i+j+2)+……\]
\[pa*F[i][j]=pa*pb*(i+j)+pa^2*pb*(i+j+1)+pa^3*pb*(i+j+2)+……\]
\[(1-pa)*S=pb(i+j)+pb(pa+pa^2+pa^3+……)\]
里面是一个等比数列求和的形式,由于有pa < 1,所以运用等比数列求和公式得到
\[(1-pa)F[i][j]=pb(i+j)+pb*\frac{pa}{1-pa}\]
\[(1-pa)F[i][j]=pb(i+j)+pa\]
\[pb*F[i][j]=pb(i+j)+pa\]
\[F[i][j]=i+j+\frac{pa}{pb}\]
所以,当i+j>=K时,运用我们推出的式子直接计算;否则,动态规划计算。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[Codeforces908D]New Year and Arbitrary Arrangement(动态规划)


HNCJ OIer