MARK on 2022.1.3:由于本人觉得“组合数学杂题选做”这篇博客太累赘了,故将其删除并将其中所有题解都单独开一篇博客写入。
首先我们贪心地想,如果现在 Yes 个数多于 No 的个数那我们肯定会猜 Yes,如果 No 个数多于 Yes 个数那我们肯定会猜 No,否则我们随便猜哪个都无所谓。我们考虑以剩余的答案为 Yes 的问题个数为横坐标,剩余的答案为 No 的问题个数为纵坐标建一个坐标系,那么不难发现一次猜答案的过程可以描述为一条 \((n,m)\to(0,0)\) 的路径,手玩一下可以发现只要你按照最优策略猜总能猜对 \(\max(n,m)\) 个,这个容易归纳证明。而你每经过一次对角线都有 \(\dfrac{1}{2}\) 的概率猜对,因此一条路径对应的期望猜对次数就是 \(\max(n,m)+\dfrac{1}{2}\text{经过对角线上元素的次数}\)。前者是个常数可以忽略,而后者可以考虑转换贡献体,枚举对角线上的元素,算出它会被多少个路径经过,然后除以总路径条数。即 \(\sum\limits_{i=1}^{\min(n,m)}\dbinom{2i}{i}·\dbinom{n-i+m-i}{n-i}·\dfrac{1}{\dbinom{n+m}{n}}·\dfrac{1}{2}\),直接计算即可。
时间复杂度线性。
const int MAXN = 1e6;
const int MOD = 998244353;
const int INV2 = 499122177;
int qpow(int x, int e) {
int ret = 1;
for (; e; e >>= 1, x = 1ll * x * x % MOD)
if (e & 1) ret = 1ll * ret * x % MOD;
return ret;
}
int n, m, fac[MAXN + 5], ifac[MAXN + 5];
void init_fac(int n) {
for (int i = (fac[0] = ifac[0] = ifac[1] = 1) + 1; i <= n; i++)
ifac[i] = 1ll * ifac[MOD % i] * (MOD - MOD / i) % MOD;
for (int i = 1; i <= n; i++) {
fac[i] = 1ll * fac[i - 1] * i % MOD;
ifac[i] = 1ll * ifac[i - 1] * ifac[i] % MOD;
}
}
int binom(int n, int k) {return 1ll * fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;}
int main() {
init_fac(MAXN); scanf("%d%d", &n, &m); int res = 0;
for (int i = 1; i <= min(n, m); i++) res = (res + 1ll * binom(i + i, i) % MOD * binom(n - i + m - i, n - i)) % MOD;
res = 1ll * res * qpow(binom(n + m, n), MOD - 2) % MOD * INV2 % MOD;
printf("%d\n", (res + max(n, m)) % MOD);
return 0;
}