===== 题解 =====

光是研究题解都研究了一晚上……

首先，我们可以得到一个结论是如果你在后面还有 $p$ 胜场和 $q$ 负场的时候使用加倍，那么你的期望收益是 $B(p,q)*\frac{p-q}{p+q}$ ，这里 $B(p,q)=\binom{n}{p}\binom{m}{q}/\binom{n+m}{p+q}$ 是超几何分布。一个直接的结论是，我们只有在 $p>q$ 的时候才会使用加倍。进一步我们可以得到，在前面使用加倍总是不会优于在后面使用的，这是因为 $B(p,q)*\frac{p-q}{p+q}=\frac{p}{p+q}*B(p,q)*\frac{p-q-1}{p+q-1}+\frac{q}{p+q}*B(p,q)*\frac{p-q+1}{p+q-1}$ ，即收益是单调不减的。

所以我们就可以得到我们的求和式子就是 $ans=\sum_{p>q \& p+q \le k}{B(p,q)*\frac{p-q}{p+q}}$

引入一下题解中的记号，记 $A(n,i)=\frac{n!}{(n-i)!}$ ，则有 $ans=\sum_{p>q \& p+q \le k}{\binom{p+q}{p}*\frac{A(n,p)*A(m,q)}{A(n+m,p+q)}*\frac{p-q}{p+q}}=\sum_{p>q \& p+q \le k}{(\binom{p+q-1}{p-1}-\binom{p+q-1}{q-1})*\frac{A(n,p)*A(m,q)}{A(n+m,p+q)}}$

我们考虑记 $C(p,q)=(\binom{p+q-1}{p-1}-\binom{p+q-1}{q-1})*A(n,p)*A(m,q)$，那么答案就可以写作 $ans=\sum_{r=1}^{k}{A(n+m,r)*\sum_{p>\lfloor r/2 \rfloor}{C(p,r-p)}}$

之后我们可以分析出 $C(p,q)=(n-p+1)*C(p-1,q)+(m-q+1)*C(p,q-1)$ 。简单说明一下，$A(n,p)=(n-p+1)*A(n,p-1),A(m,q)=(m-q+1)*A(m,q-1)$，同时 $\binom{p+q-1}{p-1}=\binom{p+q-2}{p-2}+\binom{p+q-2}{p-1},\binom{p+q-1}{q-1}=\binom{p+q-2}{q-2}+\binom{p+q-2}{q-1}$ 所以就能得到上式是对的。

然后就到了关键的地方，我们考虑一个函数 $S(r,s)=\sum_{p \ge s}{C(p,r-p)}$，那么我们要求的实际上就是 $S(r,\lfloor r/2 \rfloor +1)$ 。下面我们来正面推导一下其递推式。

首先我们利用 $C(p,q)$ 的递推式可以得到第一步展开就是 $S(r,s)=\sum_{p \ge s}{(n-p+1)*C(p-1,r-p)+(m-(r-p)+1)*C(p,(r-p)-1)}$。这个形式其实不太好直接看出来递推式，我们考虑稍微变形一下，将求和中前一部分中的 $p-1=p1$ ，那么就有：$S(r,s)=\sum_{p \ge s}{(n-p)*C(p,r-1-p)+(m-(r-p)+1)*C(p,r-1-p)}+(n-(s-1))*C(s-1,r-s)$。将求和中的两项合并起来就是：$S(r,s)=(n+m-r+1)*S(r-1,s)+(n-s+1)*C(s-1,r-s)$，也就是题解中的式子。

于是我们就可以开始递推了，每次再判断一下当前的下界有没有变大，变大就把多余的那一项减掉就行了。