【AtCoder Grand Contest 019 F】Yes or No | Mrsrz's blog

贪心，数学。

题目大意：

有 $n+m$ 个问题，其中 $n$ 个的答案为真，$m$ 个的答案为假。

你每次要回答一个问题，你会等概率回答“真”或“假”，回答完后会公布答案。

问最优策略下，回答对问题的个数的期望。

题解：

最优策略是回答题目个数较多的那个选项。这样保证了至少答对 $\max(n,m)$ 道题。

我们回答问题相当于从 $(n,m)$ 走到 $(0,0)$。在其他位置处，回答问题的情况是确定的。而在直线 $y=x$ 上时，两种决策的期望收益是相等的。此时它将有 $\frac 1 2$ 的概率额外答对一道题。

那么我们只要考虑对角线上的每个点被经过的次数即可。求出次数，乘上总方案数，乘上 $\frac 1 2$，就是这个点对答案的贡献。

可以用简单的组合数计算得出答案。

时间复杂度 $O(n+m)$。

Code：

#include<cstdio>
typedef long long LL;
const int N=1e6+5,md=998244353,iv2=(md+1)/2;
int fac[N],iv[N],n,m,ans;
inline int pow(int a,int b){
    int ret=1;
    for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
    return ret;
}
inline int C(int n,int m){return(LL)fac[n]*iv[m]%md*iv[n-m]%md;}
inline int iC(int n,int m){return(LL)iv[n]*fac[m]%md*fac[n-m]%md;}
int main(){
    scanf("%d%d",&n,&m);
    if(n<m)n^=m^=n^=m;
    for(int i=*fac=1;i<=n+m;++i)fac[i]=(LL)fac[i-1]*i%md;
    iv[n+m]=pow(fac[n+m],md-2);
    for(int i=n+m-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
    for(int i=1;i<=m;++i)
    ans=(ans+(LL)C(i+i,i)*C(n+m-2*i,n-i))%md;
    ans=(ans*(LL)iv2%md*iC(n+m,n)+n)%md;
    printf("%d\n",ans);
    return 0;
}