题目：http://codeforces.com/contest/908/problem/D
首先，设 f[i][j] 表示有 i 个 a，j 个 ab 组合的期望，A = pa / (pa + pb) , B = pb / (pa + pb)
那么 f[i][j] = A * f[i+1][j] + B * f[i][i+j]
当 i+j >= k 时，再出现一个 b 就会结束，所以此时：
f[i][j] = f[i][i+j] * B + f[i+1][i+j+1] * A * B + f[i+2][i+j+2] * A2 * B + ... + f[i+∞][i+j+∞] * A∞ * B
化简一番(等比数列求和，1 - A = B)得到 f[i][j] = i + j + A / B
于是就可以做了；
不会刷表就记忆化搜索...
注意取的答案是 dp(1,0) 而非 dp(0,0)，因为 dp(0,0) 会一直调用自己，而 dp(1,0) 可以看做是从第一个 a 出现开始算，反正前面没有 a ，对答案无影响。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const maxn=,mod=1e9+;
int k,a,b,c,f[maxn*][*maxn];
bool vis[maxn][maxn];
int pw(int a,int b)
{
int ret=;
for(;b;b>>=,a=((ll)a*a)%mod)
if(b&)ret=((ll)ret*a)%mod;
return ret;
}
int dp(int i,int j)
{
if(vis[i][j])return f[i][j];
vis[i][j]=;
if(i+j>=k)return f[i][j]=(i+j+c)%mod;
f[i][j]=((ll)a*dp(i+,j)+(ll)b*dp(i,i+j))%mod;
return f[i][j];
}
int main()
{
int pa,pb;
scanf("%d%d%d",&k,&pa,&pb);
int tmp=pw(pa+pb,mod-);
a=(ll)pa*tmp%mod; b=(ll)pb*tmp%mod;
c=(ll)a*pw(b,mod-)%mod;
// for(int i=0;i<=2*k;i++)
// for(int j=max(k-i,0);j<=2*k;j++)
// f[i][j]=f[j][i]=(i+j+c)%mod;
// for(int i=k;i>=0;i--)
// for(int j=k;j>=0;j--)
// f[i][j]=(a*f[i+1][j]+b*f[i][i+j])%mod;
printf("%d\n",dp(,));//0,0 会调用自己
//如果不是从第一个a算起,前面一堆b没用
return ;
}