1 条题解
-
0
最优策略显然是每次
YES
和NO
多的那个,一样多就任意选择。考虑如何计数。由于
YES
和NO
是等价的,所以不妨设 。对于一个答案序列,若答题过程中,从未出现
YES
和NO
一样多的情形,则必然整个过程都是NO
多,那么每次都会选择NO
,可以答对 题。考虑答题过程中,遇到
YES
和NO
都为 题的情形,对答案的贡献。每一个这样的答案序列,都会对答案产生 的贡献(因为此时任意选择,对错概率各占一半)。考虑有多少个这样的答案序列:情形发生之前,共有 道题,其中有 道是YES
,有 种情形;情形发生之后,共有 道题,其中有 道是YES
,有 种情形。而总计有 个不同的答案序列,计算期望时要除以 。
故答案为
$$M+\frac 1{2\cdot\binom{N+M}N}\sum_{i=1}^N\binom{2x}x\binom{N+M-2x}{N-x}. $$预处理阶乘与阶乘的逆元即可,时间复杂度 。
#include<bits/stdc++.h> using namespace std; const long long mod=998244353; long long power(long long m,long long n=mod-2){ if(n==0)return 1; long long tmp=power(m,n>>1); tmp=tmp*tmp%mod; if(n&1)tmp=tmp*m%mod; return tmp; } long long fac[2000001],invfac[2000001]; void init(int N=2000000){ fac[0]=1; for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod; invfac[N]=power(fac[N]); for(int i=N-1;i>=0;i--) invfac[i]=invfac[i+1]*(i+1)%mod; } inline long long C(int n,int m){ return fac[n]*invfac[m]%mod*invfac[n-m]%mod; } inline long long invC(int n,int m){ return invfac[n]*fac[m]%mod*fac[n-m]%mod; } int main(){ init(); int n,m; scanf("%d%d",&n,&m); if(n>m)swap(n,m); long long answer=0,inv2=power(2); for(int i=1;i<=n;i++) answer+=C(i<<1,i)*C(n+m-(i<<1),n-i)%mod,answer%=mod; printf("%lld\n",answer*inv2%mod*invC(n+m,n)%mod+m); return 0; }
- 1
信息
- ID
- 128
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 2
- 已通过
- 2
- 上传者