题意：给出正整数$pa,pb,k$，最开始你有一个空串，每一次你有$\frac{pa}{pa + pb}$的概率向串最后放一个$a$，有$\frac{pb}{pa + pb}$的概率向串最后放一个$b$，当串中$ab$子序列的数量$\geq K$时停止，问在操作停止时串中$ab$子序列个数的期望，对$10^9+7$取模。$pa,pb \leq 10^6,k \leq 1000$
设$f_{i,j}$表示当前串内有$i$个$a$，$j$个$ab$子序列的子序列个数期望（至于为什么不是设$a$和$b$，因为实际上$b$影响的是$ab$的数量，而只知道$a$和$b$的多少，$ab$的多少是不确定的）。可以知道转移方程为：$f_{i,j}=f_{i,i+j} \times \frac{pb}{pa+pb} + f_{i+1,j} \times \frac{pa}{pa+pb}$，但是实际上有情况一直放$a$而不放$b$，不依靠一些数学方法状态量会爆炸。
接下来是愉悦的推公式时间~~
我们可以知道当$i+j \geq k$时，只要再放一个$b$就将停止操作，那么我们的期望可以写作$\frac{pb}{pa + pb} \times \sum\limits_{p=0}^\infty [(\frac{pa}{pa + pb})^p \times (i + j + p)]$。不妨设$S = \sum\limits_{p=0}^\infty [(\frac{pa}{pa + pb})^p \times (i + j + p)]$，那么$\frac{pa}{pa + pb}S = \sum\limits_{p=0}^\infty [(\frac{pa}{pa + pb})^{p+1} \times (i + j + p)]$，相减得$\frac{pb}{pa + pb}S = i + j + \sum\limits_{p=1}^\infty (\frac{pa}{pa + pb})^p$，又由无穷递减等比数列公式得$\sum\limits_{p=1}^\infty (\frac{pa}{pa + pb})^p = \frac{\frac{pa}{pa+pb}}{1-\frac{pa}{pa+pb}}=\frac{pa}{pb}$，所以我们需要求的期望就是$i+j+\frac{pa}{pb}$
#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long
#define MAXN 1001
using namespace std;
ll dp[MAXN][MAXN];
int K , pa , pb;
inline ll ksm(ll a , ll b){
ll times = ;
while(b){
)
times = times * a % MOD;
a = a * a % MOD;
b >>= ;
}
return times;
}
inline ll calc(ll a , ll b){
if(a + b < K)
return dp[a][b];
else
)) % MOD;
}
int main(){
cin >> K >> pa >> pb;
; i >= ; i--)
; j ; j--)
dp[i][j] = (calc(i + j , j) * pb + pa * calc(i , j + )) % MOD * ksm(pa + pb , MOD - ) % MOD;
cout << calc( , );
;
}