题解
光是研究题解都研究了一晚上……
首先，我们可以得到一个结论是如果你在后面还有 p 胜场和 q 负场的时候使用加倍，那么你的期望收益是 B(p,q)∗p−qp+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)，也就是题解中的式子。
于是我们就可以开始递推了，每次再判断一下当前的下界有没有变大，变大就把多余的那一项减掉就行了。
