题解与代码 - Yes or No

## 题解

最优策略显然是每次 `YES` 和 `NO` 多的那个，一样多就任意选择。

考虑如何计数。由于 `YES` 和 `NO` 是等价的，所以不妨设 $N\leq M$。

对于一个答案序列，若答题过程中，从未出现 `YES` 和 `NO` 一样多的情形，则必然整个过程都是 `NO` 多，那么每次都会选择 `NO`，可以答对 $M$ 题。

考虑答题过程中，遇到 `YES` 和 `NO` 都为 $x$ 题的情形，对答案的贡献。每一个这样的答案序列，都会对答案产生 $\dfrac 12$ 的贡献（因为此时任意选择，对错概率各占一半）。考虑有多少个这样的答案序列：情形发生之前，共有 $N+M-2x$ 道题，其中有 $N-x$ 道是 `YES`，有 $\dbinom{N+M-2x}{N-x}$ 种情形；情形发生之后，共有 $2x$ 道题，其中有 $x$ 道是 `YES`，有 $\dbinom{2x}x$ 种情形。

而总计有 $S=\dbinom{N+M}N$ 个不同的答案序列，计算期望时要除以 $S$。

故答案为

$$
M+\frac 1{2\cdot\binom{N+M}N}\sum_{i=1}^N\binom{2x}x\binom{N+M-2x}{N-x}.
$$

预处理阶乘与阶乘的逆元即可，时间复杂度 $\Theta(N+M)$。

```cpp
// 2022.08.02

#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;
}

```

Yes or No

题解

最优策略显然是每次 YES 和 NO 多的那个，一样多就任意选择。

考虑如何计数。由于 YES 和 NO 是等价的，所以不妨设 $N\leq M$ 。

对于一个答案序列，若答题过程中，从未出现 YES 和 NO 一样多的情形，则必然整个过程都是 NO 多，那么每次都会选择 NO，可以答对 $M$ 题。

考虑答题过程中，遇到 YES 和 NO 都为 $x$ 题的情形，对答案的贡献。每一个这样的答案序列，都会对答案产生 $\dfrac 12$ 的贡献（因为此时任意选择，对错概率各占一半）。考虑有多少个这样的答案序列：情形发生之前，共有 $N+M-2x$ 道题，其中有 $N-x$ 道是 YES，有 $\dbinom{N+M-2x}{N-x}$ 种情形；情形发生之后，共有 $2x$ 道题，其中有 $x$ 道是 YES，有 $\dbinom{2x}x$ 种情形。

而总计有 $S=\dbinom{N+M}N$ 个不同的答案序列，计算期望时要除以 $S$ 。

故答案为

$M+\frac 1{2\cdot\binom{N+M}N}\sum_{i=1}^N\binom{2x}x\binom{N+M-2x}{N-x}.$

预处理阶乘与阶乘的逆元即可，时间复杂度 $\Theta(N+M)$ 。

代码

// 2022.08.02

#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;
}