AGC019 F- Yes or No 题解

题目传送门

题目大意： 有 $n+m$ 道判断题，有 $n$ 道的答案为正确，有 $m$ 道的答案为错误，进行 $n+m$ 轮提问，每次随机给你一道题，你不知道它的答案，但是你回答后他会告诉你是否答对了，问你在最优策略下期望能答对多少题。

题解

显然最优策略是每次答剩余题数较多的那类题，一顿找规律后不难发现一定能答对 $\max (n,m)$ 道题。

证明的话，不妨令 $n>m$，那么此时肯定回答正确，假如答案正确，那么 $ans+1,n-1$，否则 $ans$ 不变，$m-1$，此时 $n$ 是不变的，依然满足 $n>m$，也就是说，让 $n$ 减小的唯一条件是答对了，即只有答对了能让较大的数减小，所以肯定能答对 $\max (n,m)$ 道。

但是还有一个需要计算的地方，如果操作过程中，出现了 $n=m$，那么此时无论答对还是答错，后继状态都是 $n,n-1$（可能是 $n$ 道正确$+$ $m$ 道错误，也可能反过来，但都是一样的），即这一步无论是否答对，后面依然能答对 $n$ 个，也就是说，这一步如果答对了，那么会在 $\max (n,m)$ 的基础上额外多对 $1$ 道。

于是对于每个 $(i,i)$，统计出有多少条路径经过它，设为 $d$，那么他提供的额外期望值就是 $d/2$。

代码如下：

#include <cstdio> #include <algorithm> using namespace std; #define maxn 1000010 #define mod 998244353 int n,m; int fac[maxn],inv[maxn],inv_fac[maxn]; void FacInit(int N){ fac[0]=inv_fac[0]=inv[1]=1; for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod; for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; for(int i=1;i<=N;i++)inv_fac[i]=1ll*inv_fac[i-1]*inv[i]%mod; } int Binom(int x,int y){return 1ll*fac[x]*inv_fac[y]%mod*inv_fac[x-y]%mod;} void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);} int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;} int main() { scanf("%d %d",&n,&m);FacInit(n+m); if(n<m)swap(n,m);int ans=0; for(int i=1;i<=m;i++)add(ans,1ll*Binom(n-i+m-i,n-i)*Binom(i+i,i)%mod); ans=1ll*ans*ksm(2ll*Binom(n+m,n)%mod,mod-2)%mod;add(ans,n); printf("%d",ans); }