1 条题解

  • 0
    @ 2024-3-17 17:03:04

    最优策略显然是每次 YESNO 多的那个,一样多就任意选择。

    考虑如何计数。由于 YESNO 是等价的,所以不妨设 NMN\leq M

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

    考虑答题过程中,遇到 YESNO 都为 xx 题的情形,对答案的贡献。每一个这样的答案序列,都会对答案产生 12\dfrac 12 的贡献(因为此时任意选择,对错概率各占一半)。考虑有多少个这样的答案序列:情形发生之前,共有 N+M2xN+M-2x 道题,其中有 NxN-x 道是 YES,有 (N+M2xNx)\dbinom{N+M-2x}{N-x} 种情形;情形发生之后,共有 2x2x 道题,其中有 xx 道是 YES,有 (2xx)\dbinom{2x}x 种情形。

    而总计有 S=(N+MN)S=\dbinom{N+M}N 个不同的答案序列,计算期望时要除以 SS

    故答案为

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

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

    #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
    上传者