题解 AT2705 【[AGC019F] Yes or No】

· · 题解

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/AGC019.html。

我们将 \displaystyle \binom{N + M}{N} 种不同的答案序列，看成一条折线从 (N, M) 走到 (0, 0) 的方案数（每步只能向下或者向左走一格）。

最佳策略是：此时已知 Yes 有 a 个而 No 有 b 个，若 a > b 回答 Yes，若 a < b 回答 No，否则 a = b 回答 Yes/No 均可。

我们用横坐标表示 a，纵坐标表示 b，下图显示的就是当 a = 13 且 b = 8 时的情况。

可以发现，此时若折线向左，就相当于是本题答案为 Yes，向下则本题答案为 No。

同时，图中还有一条线：被方程 a = b 确定的斜线。

如果此时位置不在斜线上，则我们的最佳策略指出，将会回答更靠近斜线的答案。否则不妨回答 Yes。

如果回答的答案恰好与折线的走势相同，则相当于答对了一题，否则答错。

但是无论如何我们的位置，都会同折线一起前进一步，可能更靠近斜线也可能更远离斜线。

那么此时就等价于：折线经过的红色线段数量，就是我们会在这条折线对应的答案序列上产生的得分。

我们对所有的折线，将这个数值求和，然后除以 \displaystyle \binom{N + M}{N} 就是最终答案了。

折线经过的红色线段数量如何统计呢？我们不妨假设 N \ge M，也就是出发点在斜线下方的情况。

此时如果折线到达了斜线的上方，我们强行把到达斜线上方的那一部分，给折回来，折到斜线下方。

这样一变换，折线在斜线上方的部分，经过的红色线段的数量，可以发现大部分都是没变化的。

但这只是除了刚好从斜线上往左走的那些，也就是，这样折回来，损失了刚好从斜线上往左走的那一部分。

我们先不考虑那些损失，对于从未到达斜线上方的折线，显然，经过的红色线段数量恰好为 N！

那么我们只需统计刚好从斜线上往左走的期望次数。

显然只需要对斜线上的每个点，统计折线经过它的概率，乘上 1 / 2（往左走的概率）即可。

最终答案就是 N 加上这个「刚好从斜线上往左走的期望次数」。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 998244353, Inv2 = (Mod + 1) / 2;
const int MN = 1000005;

inline int qPow(int b, int e) {
    int a = 1;
    for (; e; e >>= 1, b = (LL)b * b % Mod)
        if (e & 1) a = (LL)a * b % Mod;
    return a;
}
inline int gInv(int b) { return qPow(b, Mod - 2); }

int Fac[MN], iFac[MN];
inline void Init(int N) {
    Fac[0] = 1;
    for (int i = 1; i <= N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
    iFac[N] = gInv(Fac[N]);
    for (int i = N; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;
}
inline int Binom(int N, int M) {
    if (M < 0 || M > N) return 0;
    return (LL)Fac[N] * iFac[M] % Mod * iFac[N - M] % Mod;
}
inline int Calc(int N, int M) {
    return Binom(N + M, N);
}

int N, M;

int main() {
    scanf("%d%d", &N, &M);
    if (N < M) std::swap(N, M);
    Init(N + M);
    int Ans = 0;
    for (int i = 1; i <= M; ++i) Ans = (Ans + (LL)Calc(i, i) * Calc(N - i, M - i)) % Mod;
    Ans = (LL)Ans * gInv(Calc(N, M)) % Mod;
    printf("%lld\n", (N + (LL)Ans * Inv2) % Mod);
    return 0;
}