AT_abc463_f 题解

· · 题解

啊啊啊啊啊啊啊啊这什么题啊。这是题吗啊啊啊啊啊啊啊啊。

啊啊啊啊啊啊怎么回事我咋不到 70 分钟自己做出来了，我赛时怎么没切啊啊啊啊啊啊。

啊啊啊啊啊啊啊不会吧怎么 kenkooo 评分 *2127 啊，怎么是黄色的，那我怎么做出来的，这对吗啊啊啊啊啊啊啊。

观看本篇题解前你要做好心理准备，因为定义的变量名可能会不知所云喵，且会定义较多个变量。

以及，不排除本人做复杂了的情况，所以建议浏览题解区所有题解后再选择一篇进行阅读喵。

我不会告诉你后记处有彩蛋的。

思路分析

首先令 max = \max a_i，不难发现最后的赢家的获胜场数 a'_i 只有可能是 max 或 max+1。也就是说，所有 a_i 可以分为三类：

不过这个分类没什么用就对了……

以及令 1 \le i \le n 的 a_{2i-1} 和 a_{2i} 为“一组”选手。

接下来需要定义很多后续要用到的变量，请逐个记住它们的含义，否则后面讲解的时候你可能会一头雾水喵。

定义了这么多乱七八糟的变量后，就要开始大力分讨解决问题了。

具体地，我们将答案分为两大类：\max a'_i 为 max+1 和 max 的，其中前者较为简单。

\max a'_i = max+1

在这类情况中，分类为 0 和 max-1 的选手没有任何获胜的希望，只与 max 选手有关，且 max 选手需要赢才能争取到名额。

观察前面定义的 cxx，由于一组中两位选手实力都是 max，所以不论两人胜负必贡献恰好 1 个 max+1。

于是在整场比赛结束后，a'_i = max+1 的 i 个数一定介于 [cxx,cntmax] 之间。

然后依旧是分讨，对于一个 a_x = max，其在该情况获胜的概率分别为：

给了一大坨式子却不讲原因有啥用啊？简单解释一下原因吧。

接着是 $\frac{1}{2^{cntmax-cxx}}$，这个部分与 $i$ 值**完全无关**，因为所有含 $max$ 组中要求 $max$ 获胜的概率与要求 $max$ 不获胜的概率相同，都是 $\frac{1}{2}$。但是这里为什么不是 $\frac{1}{2^{cntmax}}$ 呢？因为 $cxx$ 组 $(max,max)$ 中不论输赢都会贡献 $cxx$ 个 $max + 1$，它们不需要考虑概率，对总概率没有影响。 最后组合数 $\binom{cntmax-cxx}{i-cxx}$ 是什么意思呀，当然就是在所剩的 $cntmax-cxx$ 个含 $max$ 的组中选出 $i - cxx$ 个作为 $max + 1$ 的方案数啦！两个数都要 $-cxx$ 的原因应该不用我多说了。至于为什么当 $x$ 所在组另一人 $< max$ 时这个组合数是 $\binom{cntmax-cxx-1}{i-cxx-1}$ 呢，嗯，因为必须要选 $x$ 所在的这一组呀，所以可选范围少一个、选择数量也少一个啦。 ### $\max a'_i = max

这个是更为复杂的一种情况。由于前面已经讲过一次原因，只要你理解了前面原因的本质，后续的原因是类似的，也能自己理解，所以就不过多展开了喵。其实是因为码字有点累喵。

在这类情况中，两类选手 max-1 和 max 都有获胜的希望，但 max-1 希望自己赢而 max 必须输。注意这里的用词，max-1 是想赢（因为赢了才有机会），max 是必须输（要是赢了会有 max+1 是不被允许的）。

不过注意，当 cxx > 0 时不存在这类情况，因为 cxx 组一定会贡献一个 max+1 导致 \max a'_i 不可能是 max，所以这类情况要特判掉。

于是在这种情况下有一个固定概率系数（原谅我不会用词只能这么表达）ps = \frac{1}{2^{cntmax}}，因为我们需要确保每个 max 都输掉。

那么最坏情况下会有多少个 max，最优情况下又会有多少个 max 呢？简单推一下就能得到下界 st = cntmax + cax + cll 和上界 up = cntmax + clos，这个比较显然，可以自己证一下（基本只要知道这些变量的含义就知道为什么了喵）。

然后就是真正的大力分讨了，假设当前考虑的是 a_x，则总共存在三种情况（必要处会简要介绍原因，否则只会给出式子，读者可自行分析由来）：

详细的原因解释在此不多展开，如果有不懂的可以评论区留言，我看到后会第一时间私信解释的喵。

总结思路

把所有式子放在一起就能得到最后的答案了，注意一个 x 可能在两类情况中都有概率，此时要将得到的概率相加。

实现不难，但要小心细节。

组合数的处理需要预处理阶乘与阶乘的逆元，以及需要写好快速幂函数，因为随时需要算 2 的多少多少次方。

::::success[式子整合]{open} 对于 \max a'_i = max+1：

对于 \max a'_i = max（cxx > 0 时此项不存在）：

::::

参考实现

代码中沿用了上面用到变量名的名字，但一些临时变量的名字也可能有些不知所云，谨慎观看。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 5e5+5;
const LL MOD = 998244353;
LL n,a[N],p[N],maxa;
LL cntmax,cxx,cax,cll,clos,st,up,ps;
LL fac[N],inv[N];
LL nres,yres;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
LL QP(LL x,LL y=MOD-2){
    LL as=1;
    while(y){
        if(y&1)as=as*x%MOD;
        x=x*x%MOD,y>>=1;
    }return as;
}
void init_(){
    fac[0]=1,inv[0]=1;
    for(LL i=1;i<=2*n;i++)
        fac[i]=fac[i-1]*i%MOD;
    inv[2*n]=QP(fac[2*n]);
    for(LL i=2*n-1;i>=1;i--)
        inv[i]=inv[i+1]*(i+1)%MOD;
    return;
}
int l(int u){return 2*u-1;}
int r(int u){return 2*u;}
int ner(int u){return (u&1?u+1:u-1);}
LL C(LL x,LL y){
    if(x<y)return 0;
    LL res=fac[x]*inv[x-y]%MOD;
    return res*inv[y]%MOD;
}
int main(){
    n=read(),init_();
    for(int i=1;i<=n;i++)
        a[l(i)]=read(),a[r(i)]=read(),
        maxa=max({maxa,a[l(i)],a[r(i)]});
    for(int i=1;i<=n;i++){
        int x=a[l(i)],y=a[r(i)];
        if(x>y)swap(x,y);
        if(y==maxa)cntmax++;
        if(x==maxa)cxx++;
        if(x==maxa-1&&y==maxa)cax++;
        if(x==maxa-1&&y==maxa-1)cll++;
        if(x==maxa-1||y==maxa-1)clos++;
    }
    nres=0;
    for(LL i=cxx+1;i<=cntmax;i++){
        LL tmp=i*QP(2,cntmax-cxx)%MOD;
        LL ad=QP(tmp)*C(cntmax-cxx-1,i-cxx-1)%MOD;
        nres=(nres+ad)%MOD;
    }
    yres=0;
    for(LL i=cxx;i<=cntmax;i++){
        LL tmp=i*QP(2,cntmax-cxx+1)%MOD;
        LL ad=QP(tmp)*C(cntmax-cxx,i-cxx)%MOD;
        yres=(yres+ad)%MOD;
    }
    for(LL i=1;i<=2*n;i++){
        if(a[i]!=maxa)continue;
        //当前考虑最高为 max+1 所带来的贡献
        if(a[ner(i)]==maxa)//i in cxx
            p[i]=(p[i]+yres)%MOD;
        else p[i]=(p[i]+nres)%MOD;//i not in cxx
    }
    if(cxx){
        for(int i=1;i<=2*n;i++)
            cout<<p[i]<<" ";cout<<"\n";
        return 0;
    }
    st=cntmax+cax+cll,up=cntmax+clos;
    yres=0;
    ps=QP(QP(2,cntmax));
    for(LL i=st;i<=up;i++){
        LL tmp=i*QP(2,up-st)%MOD;
        LL ad=QP(tmp)*C(up-st,i-st)%MOD;
        yres=(yres+ad)%MOD;
    }
    nres=0;
    for(LL i=st+1;i<=up;i++){
        LL tmp=i*QP(2,up-st)%MOD;
        LL ad=QP(tmp)*C(up-st-1,i-st-1)%MOD;
        nres=(nres+ad)%MOD;
    }
    for(LL i=1;i<=2*n;i++){
        if(a[i]<maxa-1)continue;
        //当前考虑最高为 max 所带来的贡献
        if(a[i]==maxa)
            p[i]=(p[i]+ps*yres%MOD)%MOD;
        else if(a[ner(i)]<maxa-1)
            p[i]=(p[i]+ps*nres%MOD)%MOD;
        else if(a[ner(i)]==maxa-1)
            p[i]=(p[i]+ps*yres%MOD*QP(2)%MOD)%MOD;
        else p[i]=(p[i]+ps*yres%MOD)%MOD;
    }
    for(int i=1;i<=2*n;i++)
        cout<<p[i]<<" ";cout<<"\n";
    return 0;
}

::::

后记

感觉是质量挺不错的题吧，挺锻炼推式子能力的，考的就是一个严谨和细心，因为有很多不同情况需要分类讨论，且各种边界情况特殊情况都要单独考虑，稍不留神可能就多算、漏算了，要做对还是不容易的。

总而言之就是，这种题是怎么被我自己切出来的（。

彩蛋：写了两页的草稿纸。我绝不会告诉你这篇题解就是对着我的草稿纸抄的哈哈，如果你眼神够好也可以不看题解对着我的草稿纸看。唉不是我怎么公开爆字迹了啊啊啊。

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！