[AGC019F] Yes or No
zhehaya
·
·
题解
首先注意期望的重要性质，注意X为随机变量。
$E(X+Y)=E(X)+E(Y)$。
$X,Y$独立时$E(XY)=E(X)E(Y)$。
---
首先考虑暴力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$ 的局面数”为
$$\displaystyle\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}\displaystyle\sum_{k=1}^{min(m,n)}\frac{\binom{n-k+m-k}{n-k}\binom{2k}{k}}{\binom{n+m}{n}}$$
AC代码如下，注意逆元等细节。
```c++
#include <bits/stdc++.h>
#define MOD 998244353
#define int long long
using namespace std;
int n, m, jc[2145141], ans;
int qpow(int a, int b) {//快速幂
int ans = 1;
while (b) {
if (b & 1)
ans = 1ll * ans * a % MOD;
b >>= 1;
a = 1ll * a * a % MOD;
}
return ans % MOD;
}
void yu() {//阶乘预处理
jc[0] = 1;
for (int i = 1; i <= 2000011; i++)
jc[i] = 1ll * jc[i - 1] * i % MOD;
}
int ni(int x) {//求逆元
return qpow(x, MOD - 2);
}
int C(int n, int m) {//求组合数
if (n < m || n < 0)
return 0;
if (!m)
return 1;
return 1ll * jc[n] * ni(jc[m]) % MOD * ni(jc[n - m]) % MOD;
}
signed main() {
cin >> n >> m;
yu();
if (m > n)
swap(m, n);
for (int k = 1; k <= m; k++) {
ans += (C(n - k + m - k, n - k) % MOD * C(2 * k, k) % MOD);
ans %= MOD;
}
ans *= (ni(C(n + m, n)) % MOD);
ans %= MOD;
ans *= (ni(2) % MOD);
ans %= MOD;
ans += n;
ans %= MOD;//同上公式
cout << ans;
}
```