[数学记录]AT2705 [AGC019F] Yes or No

**题意** ：有 $n+m$ 个问题，已知其中有 $n$ 个问题的答案是 $\rm Yes$，$m$ 个问题的答案是 $\rm No$。 当你回答一个问题之后，会知道这个问题的答案，求最优策略下期望答对多少。 答案对 $998244353$ 取模。 $n,m\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 先考虑最优策略，不难发现，若剩下的 $\rm Yes$ 多就答 $\rm Yes$，$\rm No$ 多就答 $\rm No$ 即可。 以 $(n,m)$ 表示还剩 $n\times{\rm Yes},m\times{\rm No}$ ，将一条答案序列看做 $n\times m$ 的网格上的一条路径。 如果走到了 $(u,v)$ ，则决策如下 : - $u<v$ ，猜下一步是 $(u,v-1)$ ，期望收益为 $\binom{u+v}{v}$ - $u>v$ ，猜下一步是 $(u-1,v)$ ，期望收益为 $\binom{u+v}{u}$ - $u=v$ ，随便猜，期望收益均为为 $1/2$。 将我们猜对的总次数除以 $\binom{n+m}{m}$ 即为答案。 并不容易将三部分分别统计，考虑化简。 不妨设 $n\geq m$ ，将一条路径中 $(u,v)(u<v)$ 的部分沿着 $u=v$ 翻折，变为 $u\geq v$ 的情况。 不难发现，转化后的路径每一步的期望收益都没有变。 且 $u>v$ 的决策是全 $\rm Yes$，容易发现（对于转化后的路径 $u=v$ 时答案必然不是 $\rm Yes$），此时的收益总是 $n$。 当 $u=v$ 时，每走一步的收益是 $1/2$ ，需要计算所有路径经过 $u=v$ 的次数总和。 对于点 $(i,i)$ ，经过它+的方案数为 $\binom{2i}{i}\binom{n+m-2i}{n-i}$。 所以，答案为 $$n+\dfrac{1}{2\binom{n+m}{m}}\sum\limits_{i=0}^m\binom{2i}{i}\binom{n+m-2i}{n-i}$$ ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 1000500 using namespace std; const int mod=998244353; ll powM(ll a,int t=mod-2){ ll ret=1; while(t){ if (t&1)ret=ret*a%mod; a=a*a%mod;t>>=1; }return ret; } ll fac[MaxN],ifac[MaxN]; ll C(int n,int m) {return fac[n]*ifac[m]%mod*ifac[n-m]%mod;} void Init(int n) { fac[0]=1; for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; ifac[n]=powM(fac[n]); for (int i=n;i;i--) ifac[i-1]=ifac[i]*i%mod; } int n,m; int main() { scanf("%d%d",&n,&m); if (n<m)swap(n,m); Init(n+m); ll ret=0; for (int i=1;i<=m;i++) ret=(ret+C(2*i,i)*C(n+m-2*i,n-i))%mod; ret=ret*powM(2*C(n+m,m)%mod)%mod; printf("%lld",(ret+n)%mod); return 0; } ```