[AGC019F] Yes or No

首先期望的重要性质，注意\(X\)为随机变量

\(E(aX)=aE(X)\)

\(E(X+Y)=E(X)+E(Y)\)

\(XY\)独立时\(E(XY)=E(X)E(Y)\)

题面翻译

有 \(N+M\) 个问题，其中有 \(N\) 个问题的答案是 YES，\(M\) 个问题的答案是 NO。当你回答一个问题之后，会知道这个问题的答案，求最优策略下期望对多少。

答案对 \(998244353\) 取模。

题解

首先考虑暴力dp，考虑运用性质2，设\(f(n,m)\)表示n，m时的期望，我们选择n，m中最多的来选择，此随机变量分为两部分：当前选的和之后选的；当前选因为最大的，可以得出当前选的期望为：$ \frac{\max (n,m)}{m+n}\(,之后选的有可能这个是少了一个yes或少了一个no，考虑用概率来考虑之后选的，期望为：\)\frac{n}{m+n} f(n-1,m)+\frac{m}{m+n}f(n,m-1)$。

所以总递推式子为\(f(n,m)=\frac{\max (n,m)}{m+n}+\frac{n}{m+n} f(n-1,m)+\frac{m}{m+n}f(n,m-1)\)。

尝试优化，设\(m\leq n\),我们可以仍然考虑单个给我们带来的期望，当前局面若为 YES,猜对了有贡献;当前局面若为 NO,没猜对无贡献但是我们却可以让m减小，也就是NO时n仍然可以保持最大。考虑期望最坏的情况，此时我们一直没有猜对，\(m\)一直减小减小到了0，最后全是\(n\)，这样就可以猜对n次，而其它不同的情况的猜对次数肯定比这个高，所以期望保底有n。

需要注意的是，即使前期一直猜对导致\(n=m\)，期望仍不会低于\(n\)，因为\(m>n\)的局面我们只需转化为\(n>m\)的局面来看待发现期望的变化仍然一样。

这是我们的出来了由\(n>m\)局面得来的保底期望，剩下的便是\(n=m\)时的局面，\(n=m\)时我们选择哪一个的概率都是\(\frac{1}{2}\),所以若是单次选择，期望便是\(\frac{1}{2}\)。

考虑这种局面的总期望，由于选择对错的随机变量和局面数的随机变量无关，由\(E(XY)=E(X)E(Y)\)，我们可以得出来\(n=m\)所带来的贡献。其实就是拿“期望出现的 \(n=m\) 的局面数”乘上“期望单次选择对错"（即\(\frac{1}{2}\))。

那么我们现在的问题就只差求出来“期望出现的 \(n=m\) 的局面数”，这个东西改咋子求嘞?可以轻易发现这东西就是出现\(n=m\) 的局面的概率（因为不出现\(n=m\) 的局面的概率乘上0没了）。设这个点为\((k,k)\),也就是说我们通过减n或m减到了\((k,k)\),也就是说总共减去了\(n-k+m-k\),而我们究竟有多少种方案走到这个地方呢？可以知道有\(n-k\)次yes，所以我们可以得出有\(\binom{n-k+m-k}{n-k}\)种方案走到(当然要是你考虑从no出发了话下面就是\(m-k\))，但是因为是要求全程的方案（也就是经过，而不只是到达），所以我们又要从\((k,k)\)走到\((0,0)\),这个好求，总距离\(2k\),\(k\)个yes,即\(\binom{2k}{k}\)。综上，经过的总方案为\(\binom{n-k+m-k}{n-k}\binom{2k}{k}\).

只需要再除去总路径的方案数就大功告成了。总距离为\(n+m\),选yes的有\(n\)，也就是说总方案数为\(\binom{n+m}{n}\)。所以得出“期望出现的 \(n=m\) 的局面数”为\(\sum_{k=1}^{min(m,n)}\frac{\binom{n-k+m-k}{n-k}\binom{2k}{k}}{\binom{n+m}{n}}\)

ok总结一下吧，总共期望就是：

\(max(n,m)+\frac{1}{2}\sum_{k=1}^{min(m,n)}\frac{\binom{n-k+m-k}{n-k}\binom{2k}{k}}{\binom{n+m}{n}}\)

来自黄赫哲的md笔记。