# [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 .

## 解决思路

$F[i][j]=F[i][j+1]*pa+F[i+j][j]*pb$

$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+……)$

$(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}$

HNCJ OIer 一枚