Description
给定 \(k,pa,pb\)，有一初始为空的序列。
每次有 \(\dfrac{pa}{pa+pb}\) 的概率往序列后面加一个 a。
每次有 \(\dfrac{pb}{pa+pb}\) 的概率往序列后面加一个 b。
当出现大于等于 \(k\) 个形如 ab 的子序列（a 和 b 不一定相邻）时停止。
求序列最终的 ab 子序列期望数。
Solution
为了更加简洁，文中的 \(pa\) 指题意中的 \(\dfrac{pa}{pa+pb}\)，\(pb\) 指 \(\dfrac{pb}{pa+pb}\)。
看到求期望，可以先试着写写 dp。
设 \(f_{i,j,t}\) 表示有 \(i\) 个 a、\(j\) 个 b、\(t\) 个 ab 时的期望。
发现当前有 \(i\) 个 a 时，再加一个 b 会产生 \(i\) 个 ab，与之前 b 的数量无关，所以省去一维 dp。
设 \(f_{i,j}\) 表示有 \(i\) 个 a、\(j\) 个 ab 时的期望。
由于我们只知道终止状态，所以倒推会更好写且容易理解。
\(f_{i,j}\) 有 \(pa\) 的概率加 a 变为 \(f_{i+1,j}\)，有 \(pb\) 的概率加 b 变为 \(f_{i,j+i}\)，得出转移方程：
答案即为 \(f_{1,0}\)。
接下来是本题最难部分，求满足终止条件的 \(f\) 值。
终止条件为 \(i+j\ge k\)，此时只要再加一个 b 就可以终止。
然而在加 b 前可能有若干个 a，无法确定 a 的数量，所以要开始推式子。
Sol1
这种方法用了等比数列的思想。
\[f_{i,j(i+j\ge k)}=i+j+\sum\limits_{x=0}^\infty pa^x\times pb\times x \]\(x\) 为 a 的出现次数，a 每多在 b 前出现一次，最后的 ab 就会多一个，所以总共加了 \(i+j+x\) 个 ab。
继续推：
\[=i+j+pb\times\sum\limits_{x=0}^\infty pa^x\times x \]\[=i+j+(1-pa)\times\sum\limits_{x=0}^\infty pa^x\times x \]设 \(T=\sum\limits_{x=0}^\infty pa^x\times x\)。
\[\therefore pa\times T=\sum\limits_{x=1}^\infty pa^x\times (x-1) \]\(x\) 变为 \(x-1\) 的原因是 \(x\) 变为 \(1\) 开始。
\[\because T=\sum\limits_{x=1}^\infty pa^x\times x+pa^0\times0=\sum\limits_{x=1}^\infty pa^x\times x \]\[\therefore (1-pa)\times T=\sum\limits_{x=1}^\infty pa^x \]设 \(S=\sum\limits_{x=0}^\infty pa^x\)。
\[\therefore pa\times S=\sum\limits_{x=1}^\infty pa^x \]\[\because S=\sum\limits_{x=1}^\infty pa^x+pa^0=\sum\limits_{x=1}^\infty pa^x+1=T+1 \]\[\therefore (1-pa)S=pa^0=1 \]\[S=\dfrac{1}{1-pa}=T+1 \]\[\therefore T=\dfrac{1}{1-pa}-1=\dfrac{pa}{pb} \]\[\therefore f_{i,j(i+j\ge k)}=i+j+\dfrac{pa}{pb} \]Sol2
对于 \(f_{i,j}\) 和 \(f_{i+1,j}\)（\(i+j\ge k\)）：
由于后面的 b 终止前，新的 a 产生的多余 ab 期望数都是一样的。
所以两期望的区别只有当前 a 相差 \(1\) 造成的期望 \(1\)。
即 \(f_{i+1,j}=f_{i,j}+1\)。
\[\because i+j\ge k \]\[\therefore f_{i,j+i}=i+j \]\[\therefore f_{i,j}=pa\times(f_{i,j}+1)+pb\times(i+j) \]\[(1-pa)\times f_{i,j}=pa+pb\times(i+j) \]\[pb\times f_{i,j}=pa+pb\times(i+j) \]\[f_{i,j}=\dfrac{pa}{pb}+i+j \]Code
#include<bits/stdc++.h>
using namespace std;
#define mo 1000000007
#define int long long
int k,a,b,pa,pb;
int f[1010][1010];
int po(int x,int y){
int z=1;
while(y){
if(y%2) z*=x;
x*=x;
x%=mo,z%=mo;
y/=2;
}
return z;
}
signed main(){
cin>>k>>a>>b;
pa=a*po(a+b,mo-2)%mo;
pb=b*po(a+b,mo-2)%mo;
for(int i=k;i>=1;i--){
for(int j=k;j>=0;j--){
if(i+j>=k){
f[i][j]=pa*po(pb,mo-2)%mo+i+j;
f[i][j]%=mo;
}else{
f[i][j]=f[i+1][j]*pa%mo+f[i][j+i]*pb%mo;
f[i][j]%=mo;
}
}
}
cout<<f[1][0];
return 0;
}