题解：P17856 [LBA-OI R6 D] 奶龙游戏

· · 题解

对于一种分配方式，我们考虑可以怎么贡献。由于 Alice 后选，并且知道 Bob 是什么，所以它可以直接确定获胜几场，但是这个获胜肯定是有上下限，我们尝试推出这个上下限先，然后根据上下限让每种方案去贡献，说不定还会有一些神秘性质。

首先假设 Alice 的集合是 a，Bob 是 b，a,b 都是有序的。我们发现 Alice 要赢得多肯定是找到一个 k，\forall i\in [1,k]，我们的分配满足 a_{n-k+i}>b_i，那么这个最大的 k 就是 Alice 的上界，因为这样的分配方式是最优的。

同理我们可以找到下界，也就是 Bob 最多赢 j 场，也就是 Alice 至多 n-j 场。

我们可以合理猜想一下，这个是一段连续区间，即 \forall n-j\le m\le k 都能找到一组分配方案使得 Alice 赢 m 场，这个是因为 \forall i\in [1,m],a_{n-m+i}>a_{n-k+i}>b_i，并且 \forall i\in [1,n-m],a_{i}<b_{n-j+i}<b_{m+i}，故 m 场可以操控。

我们现在考虑怎么统计每个方案的贡献，每个方案贡献的是一段区间 [l,r]。对于一种划分，都可以转成把数动态插入。

我们模拟插入过程，每次就是将 1\sim 2n 的 2n 个数从小到大插入到 a,b 两个最终长度为 n 的序列中，当前插入到 i，len_a-len_b=c_i，那么说明 b 后面会比 a 多 c_i 个 >i 的数，所以 a 至少输 c_i 场，容易猜到，l=max_{i=1}^{2n} c_i。

同理，也可以得到 r。

于是问题可以得到转化，每次插入一个数，相当于给和 +1,-1，那么对于每个 k=0\sim n，就相当于就是求最后和 =0 并且过程中不可超过 k，也不可能低于 n-k 的方案数。

这个形式就可以进一步进行经典的转化，将其转化成坐标轴上，每次 x+1 或者 y+1，要求走到 (n,n) 且不经过 y=x+k 和 y=x-(n-k) 的方案数，发现不存在同时经过这两条线，所以可以分开计算。

接下来就是经典的反射容斥，答案即是 {2n\choose n}-{2n\choose n-k-1}-{2n\choose k-1}，最后算概率就除以 2n\choose n 即可。

code：

const int N=4e6+5,mod=998244353;

int n,frac[N],inv[N];

int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}

int C(int n,int m){
    if(n<0 || m<0 || n<m) return 0;
    if(m==0 || n==m) return 1;
    return frac[n]*inv[m]%mod*inv[n-m]%mod;
}

signed main(){
    IOS;
    cin>>n;
    frac[0]=frac[1]=1,inv[0]=inv[1]=1;
    for(int i=2;i<=2*n;i++) frac[i]=frac[i-1]*i%mod;
    inv[2*n]=qpow(frac[2*n],mod-2);
    for(int i=2*n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
    int bs=C(2*n,n),ibs=qpow(bs,mod-2);
    for(int k=0;k<=n;k++){
        int ans=(bs-C(2*n,k-1)-C(2*n,n-k-1)+2*mod)%mod;
        cout<<ans*ibs%mod<<"\n";
    }
    return 0;
}