AGC019F Yes or No
阅读原文时间:2023年09月07日阅读:1

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

数据范围:\(1\le N, M\le 5\times 10^5\)。

首先每次必定去猜那个个数更多的问题。用点 \((x, y)\) 表示剩余 \(x\) 个 YES 和 \(y\) 个 NO ,在这个网格上面随机走,每次如果你在直线 \(y = x\) 上方,向下走得到 \(1\) 的收益,否则向左走得到 \(1\) 的收益。最终一定走到 \((0, 0)\)。那么注意到不在 \(y = x\) 上的时候获得的总收益是固定的,为 \(\max\{n, m\}\)。这是因为可以想象当穿过 \(y = x\) 以后就把整个图对称一下,最后相当于只有横着走获得收益或者只有竖着走获得收益,一直走到 \(0\)。接下来考虑计算在 \(y = x\) 上的收益,期望是碰到这个直线的次数除以 \(2\),很容易计算。

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章