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

考虑最优方案是什么?当现在处在 $(x,y)$ 点的时候,显然是选取大的一方。如果 $x=y$ ,因为剩下的序列是由等量的 YesNo 组成的,所以当前题的正确答案为 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 的路径” 个数了,因为 YesNo 是等价的,所以这个值显然为:
$$
\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;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code