题解：AT_agc019_f [AGC019F] Yes or No

· · 题解

考虑我们的策略：最优策略一定是当前剩余的 Yes 多的时候回答 Yes，No 多的时候回答 No，这可以通过简单的分析每一步回答 Yes/No 的期望导出。

画出折线图，x,y 分别表示剩余的 Yes/No 个数，我们不在 y=x 直线上时猜测是一定的，也一定会带来 \max(n,m) 的贡献，而在折线上时猜中的概率是 \frac{1}{2}，所以答案可以表示为：

\dfrac{\sum_{i=1}^{\min(n,m)} \binom{2i}{i}\binom{n-i+m-i}{n-i}}{2}

EI 还为本题给出了一个帅气的恒等式，我们来证明它，不妨设 n\leq m！

\begin{align} &=\sum_{i\geq1} \binom{2i}{i}\binom{n+m-2i}{n-i} \\ &= \sum_{i\geq1}\binom{2i}{i}[x^{n-i}](1+x)^{n+m-2i}\\ &= [x^n]\sum_{i\geq 1}\binom{2i}{i}(1+x)^{n+m-2i}x^i\\ &= [x^n](1+x)^{n+m}\sum_{i\geq 1}\binom{2i}{i}\left(\frac{x}{(1+x)^2}\right)^i \\ \end{align}

我们熟知 \sum_{i\geq 0}\binom{2i}{i}t^i=\frac{1}{\sqrt{1-4t}}，又有 \frac{1}{\sqrt{1-\frac{4x}{(1+x)^2}}}=\frac{1+x}{1-x}，所以：

\begin{align} &= [x^n](1+x)^{n+m}\left( \frac{1+x}{1-x}-1 \right) \\ &= 2[x^{n-1}]\frac{(1+x)^{n+m}}{1-x} \\ &=2 \sum_{i=0}^{n-1}\binom{n+m}{i} \end{align}

证毕！