New Year and Arbitrary Arrangement
思路：
期望题果然还是恶心呀！
我们设 \(f[i][j]\) 表示当串中有 \(i\) 个 \(a\) 和 \(j\) 个 \(ab\) 时的方案数。为了方便，设 \(A=\dfrac{P_a}{P_a+P_b},B=\dfrac{P_b}{P_a+P_b}\)。
显然，可以这样转移：
\[f[i][j]=f[i+1][j]\times A+f[i][i+j]\times B \]因为，如果串后面加上一个 \(a\)，概率是 \(A\)，并且加完后唯一的影响就是 \(i+1\)；如果加入一个 \(b\)，概率是 \(B\)，加完后前面每一个 \(a\) 都会与这个 \(b\) 形成一对 \(ab\)。
那么边界条件呢？
显然，当 \(i+j\geq k\) 时，只要再往后面加入一个 \(b\)，过程就停止了。
则这个的期望长度应该是：
\[B\times \sum\limits_{a=0}^{\infty}(i+j+a)\times A^a \]其中，枚举的这个 \(a\) 是在终于搞出一个 \(b\) 前，所刷出的 \(a\) 的数量。
为了方便，我们设 \(i+j=c\)，并用 \(i\) 替换 \(a\)。即：
\[B\times \sum\limits_{i=0}^{\infty}(c+i)\times A^i \]因为 \(A+B=1\)，我们可以用 \((1-A)\) 代 \(B\)。
即：
\[(1-A)\times \sum\limits_{i=0}^{\infty}(c+i)\times A^i \]拆开括号得:
\[\sum\limits_{i=0}^{\infty}(c+i)\times A^i-\sum\limits_{i=0}^{\infty}(c+i)\times A^{i+1} \]一上来直接 \(\infty\) 有些不直观，我们用 \(n\) 替换掉:
\[\sum\limits_{i=0}^n(c+i)\times A^i-\sum\limits_{i=0}^n(c+i)\times A^{i+1} \]在第二个式子里面用 \(i+1\) 代掉 \(i\):
\[\sum\limits_{i=0}^n(c+i)\times A^i-\sum\limits_{i=1}^{n+1}(c+i-1)\times A^i \]将第一个 \(\Sigma\) 中 \(i=0\) 的情况和第二个 \(\Sigma\) 中 \(i=n+1\) 的情况分别提出：
\[c+\sum\limits_{i=1}^n(c+i)\times A^i-\sum\limits_{i=1}^n(c+i-1)\times A^i-(c+n)\times A^{n+1} \]合并两个 \(\Sigma\)：
\[c+\sum\limits_{i=1}^nA^i-(c+n)\times A^{n+1} \]套等比数列求和公式，注意要先提出一个 \(A\) 使首项为为一。
\[c+A\times \dfrac{1-A^n}{1-A}-(c+n)\times A^{n+1} \]注意到 \(1-A=B\)：
\[c+A\times \dfrac{1-A^n}{B}-(c+n)\times A^{n+1} \]现在，考虑 \(n\rightarrow\infty\) 的情况，即：
\[\lim\limits_{n\rightarrow\infty}c+A*\dfrac{1-A^n}{B}-(c+n)*A^{n+1} \]注意到 \(0<A<1\)，因此
\(\lim\limits_{n\rightarrow\infty}A^n=0\) 带入发现：
处理一下 \(c+\dfrac{A}{B}\) 注意到我们一开始的定义了吗？
\[A=\dfrac{P_a}{P_a+P_b},B=\dfrac{P_b}{P_a+P_b} \]以及 \(c=i+j\) 代入得：
\[i+j+\dfrac{P_a}{P_b} \]也就是说，边界条件就是 \(f[i][j]=i+j+\dfrac{P_a}{P_b}(i+j\geq k)\)！！！
再搬出我们一开始的转移式：
\[f[i][j]=f[i+1][j]\times A+f[i][i+j]\times B \]完事。
哦，另外，还要思考一下答案到底是 \(f[0][0]\) 还是 \(f[1][0]\)。
因为一开始的那些 \(b\)，无论来多少个都是没用的，因此不如直接从 \(f[1][0]\) 开始。事实上，你如果把转移式代回去或者打个表的话，你会发现就有 \(f[0][0]=f[1][0]\)。
复杂度 \(O(k^2+\log mod)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e3+100;
int n,a,b,c,A,B;
int f[N][N];
int ksm(int x,int y){
int z=1;
for(;y;(x*=x)%=mod,y>>=1) if(y&1) (z*=x)%=mod;
return z;
}
int dfs(int x,int y){
if(x+y>=n) return x+y+c;
if(f[x][y]!=-1) return f[x][y];
int &res=f[x][y];
res=0;
(res+=dfs(x+1,y)*A%mod)%=mod;
(res+=dfs(x,x+y)*B%mod)%=mod;
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>a>>b;
memset(f,-1,sizeof(f));
A=a*ksm(a+b,mod-2)%mod;
B=b*ksm(a+b,mod-2)%mod;
c=a*ksm(b,mod-2)%mod;
cout<<dfs(1,0);
return 0;
}