题解：AT_abc483_g [ABC483G] Qualification

· · 题解

如果 P_i,Q_i \le K，那么 i 在两种方法中必定都会被选，设满足这个条件的 i 的个数为 r，枚举这个数。

为了方便计算，下面仅计算期望 E，其中若满足这个条件的 i 的个数不为 r，那么该部分以 0 计入期望。

于是 ans = \sum_{r=0}^{K}(N!)^2\times E。

因为 P_i \le K 的个数为 K，Q_i \le K 的个数为 K，同时满足 P_i,Q_i \le K 的个数为 r，则满足 Q_i \le K,P_i > K 的个数为 K-r，满足这个条件的概率可以由以下式子得到。

\frac{\binom{K}{r}\times\binom{N-K}{K-r}}{\binom{N}{K}}

其中 \binom{K}{r} 表示 P_i \le K 的部分中有恰好 r 个满足 Q_i \le K 的方案数，\binom{N-K}{K-r} 表示 P_i > K 的部分中有恰好 K-r 个满足 Q_i \le K 的方案数。\binom{N}{K} 为总方案数。

到这里，我们已经保证了 P_i \le K \lor Q_i \le K 的部分，共 2K-r 个数，还剩 N - 2K + r 个数。对于剩下的数，发现选入方法 1 的满足 Q_i 在剩下的数中前 r 小，选入方法 2 的满足 P_i 在剩下的数中前 r 小。对于 Q_i 前 r 小的数，能贡献答案当且仅当不被 2 选，也就是 P_i 不在前 K 小，每个数贡献答案的概率为 1-\frac{r}{N-2K+r} = \frac{N-2K}{N-2K+r}。可以得到这 r 个数（Q_i 在剩下的数中前 r 小）对答案的期望贡献为 r\frac{N-2K}{N-2K+r}。

E = \frac{\binom{K}{r}\times\binom{N-K}{K-r}}{\binom{N}{K}}r\frac{N-2K}{N-2K+r}

之后答案就很好算了。

ans = (N!)^2\sum_{r=0}^{K} \frac{\binom{K}{r}\times\binom{N-K}{K-r}}{\binom{N}{K}}r\frac{N-2K}{N-2K+r}

:::info[code]

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e6 + 5,p = 998244353;
ll A[N + 5],I[N + 5];
ll t,n,k,ans;
ll qpow(ll x,ll y){
    ll res = 1,w = x;
    while(y){
        if(y & 1){
            res = res * w % p;
        }
        w = w * w % p;
        y >>= 1;
    }
    return res;
}
ll C(ll x,ll y){
    if(x < y || y < 0) return 0;
    return A[x] * I[y] % p * I[x-y] % p;
}
ll D(ll x,ll y){
    if(x < y || y < 0) return 0;
    return I[x] * A[y] % p * A[x-y] % p;
}
int main(){
    A[0] = 1;
    for(ll i = 1;i <= N;++i) A[i] = A[i-1] * i % p;
    I[N] = qpow(A[N],p-2);
    for(ll i = N - 1;i >= 0;--i) I[i] = I[i+1] * (i+1) % p; 
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        ans = 0;
        for(ll i = 0;i <= k;++i){
            ans += (n-2*k)*qpow(n-2*k+i,p-2)%p*i%p*C(k,i)%p*C(n-k,k-i)%p*D(n,k)%p;  
            ans %= p;
        }
        ans = ans * A[n] % p;
        ans = ans * A[n] % p;
        ans = (ans % p + p) % p;
        printf("%lld\n",ans);
    }   
    return 0;
}

:::