# [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}$

## 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1010;
const int Mod=1e9+7;
const int inf=2147483647;

ll K,a,b;
ll F[maxN][maxN];

ll QPow(ll x,ll cnt);

int main()
{
ios::sync_with_stdio(false);
cin>>K>>a>>b;
ll invab=QPow(a+b,Mod-2);
ll inva=QPow(a,Mod-2),invb=QPow(b,Mod-2);
for (int i=K;i>=0;i--)
for (int j=K;j>=0;j--)
if ((i!=0)||(j!=0))
{//分情况讨论
if (i+j>=K) F[i][j]=(ll)(i+j)+(ll)a*invb%Mod;
else F[i][j]=((ll)a*F[i][j+1]%Mod*invab%Mod+(ll)b*F[i+j][j]%Mod*invab%Mod)%Mod;
}
cout<<F[0][1]<<endl;
return 0;
}

ll QPow(ll x,ll cnt)
{
ll ret=1;
while (cnt)
{
if (cnt&1) ret=ret*x%Mod;
x=x*x%Mod;
cnt=cnt>>1;
}
return ret;
}


HNCJ OIer 一枚