【题解】AGC019F 组合数学 — Qiuly

考虑用 $(n,m)$ 表示 现在还剩下 $n$ 道答案为 Yes 的题、$m$ 道答案为 No 的题。这样对于所有的序列，对应的就是 $(n,m)\rightarrow (0,0)$ 的一条只 往下或往右 走的路径。

考虑最优方案是什么？当现在处在 $(x,y)$ 点的时候，显然是选取大的一方。如果 $x=y$ ，因为剩下的序列是由等量的 Yes 和 No 组成的，所以当前题的正确答案为 Yes 和为 No 的概率是一样的，钦定选 No 好了。

考虑一条平凡的路径——即不经过直线 $y=x$ 的路径，这样的路径不会遇见 $x=y$ 的情况，此时的方案是什么呢？假设 $n>m$ ，因为在过程中 Yes 一直都比 No 多，按照策略来的话，会一直回答 Yes，此时答对的题数是 $\max(n,m)$ 。$m>n$ 的情况同理。

如果经过 $y=x$ 了呢？不妨考虑 n=m=1 的情况，此时按照最优策略来的话，期望答对的题数是 1.5 ，因为有一条路径在直线蒙 Yes 的时候蒙对了。具体的，仍然考虑 $n>m$ 的情况，不经过直线的话答案为 No 的题是都答不对的，但是现在在点 $(i,i)$ 上，如果当前路径下一题的答案为 Yes ，意味着下一步会进入 $(i-1,i)$，接下来无论如何，倒数第 $i$ 到答案为 No 的题一定会被回答正确：显然当前局面是原局面的一个子问题，于是便会为答案做出 $1$ 的贡献。

具体的，考虑一个直线上的点 $(i,i)$ 的贡献，现在要做的就是统计” 经过 $(i,i)$ 且下一题答案为 Yes 的路径” 个数了，因为 Yes 和 No 是等价的，所以这个值显然为：
$$
\frac{1}{2}{n+m-2i\choose n-i}{2i\choose i}
$$
于是答案为：
$$
\max(n,m)+\sum_{i=1}^{n}\frac{1}{{n+m\choose n}}\left(\frac{1}{2}{n+m-2i\choose n-i}{2i\choose i}\right)
$$
时间复杂度 $O(n)$ 。

const int N=1e6+5;
int n,m,fac[N],inv[N];

inline int C(int n,int m) {
    if(n<m||n<0||m<0) return 0;
    return mul(fac[n],mul(inv[m],inv[n-m]));
}

inline void init(int L=N-5) {
    fac[0]=1;
    lep(i,1,L) fac[i]=mul(fac[i-1],i);
    inv[L]=modpow(fac[L],mod-2);
    rep(i,L,1) inv[i-1]=mul(inv[i],i);
}

inline void solve() {
    int ans=0,l=min(n,m);

    lep(i,1,l) pls(ans,mul(C(n+m-(i<<1),n-i),C(i<<1,i)));
    ans=mul(ans,modpow(2,mod-2));
    ans=mul(ans,mul(inv[n+m],mul(fac[n],fac[m])));

    printf("%d\n",add(ans,max(n,m)));
}

int main() {
    IN(n,m);

    init();
    solve();
    return 0;
}