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

· · 个人记录

题意 ：有 n+m 个问题，已知其中有 n 个问题的答案是 \rm Yes，m 个问题的答案是 \rm No。

当你回答一个问题之后，会知道这个问题的答案，求最优策略下期望答对多少。

答案对 998244353 取模。

------------ 先考虑最优策略，不难发现，若剩下的 $\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}

将我们猜对的总次数除以 \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} 
#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;
}