题解：AT_abc483_g [ABC483G] Qualification

· · 题解

不妨设 A 中 1\sim k 是优秀的，这个的概率是 \frac{1}{\binom{n}{k}}，最后处理。

根据你的计数直觉，不难发现要枚举 A,B 优秀集合的交集大小 r。我们从 1\sim k 中选出 r 个人在 B 中也优秀，然后从 k+1\sim n 中选出 k-r 个其它在 B 中优秀的人，这些都是系数，简单计算。并集里的人一定对答案没有贡献。

接下来一步，显然是对每个人计算它在方案 1 中被选择，而没在方法 2 中被选择的概率，直接相加就是期望；并集之外的那 n-2k+r 个人是独立的。对于每个人来说，它做贡献的概率，显然是 \frac{r(n-2k)}{(n-2k+r)^2}（然后乘以人数，会消去一个 n-2k+r），也即在 A 中被选且在 B 中没被选的概率。

你发现枚举 r 竟然就做完了？复杂度 O(n)。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define mod 998244353
#define MAXN 2000005

int n,k,fac[MAXN],inv[MAXN],ifac[MAXN];

inline int C( int n , int m ){ return n >= m && n >= 0 && m >= 0 ? fac[n] * ifac[m] % mod * ifac[n - m] % mod : 0; }

inline void solve(){
    scanf("%lld%lld",&n,&k);
    if( n == 2 * k ){ puts("0"); return; }
    int ans = 0;
    for( int r = 1 ; r <= k ; r ++ )
        ans = ( ans + C( k , r ) * C( n - k , k - r ) % mod * r % mod * inv[n + r - 2 * k] % mod ) % mod;
    printf("%lld\n",ans * fac[n] % mod * fac[k] % mod * fac[n - k] % mod * ( n - 2 * k ) % mod);
}

signed main(){
    fac[0] = inv[1] = ifac[0] = 1;
    for( int i = 1 ; i < MAXN ; i ++ ) fac[i] = fac[i - 1] * i % mod;
    for( int i = 2 ; i < MAXN ; i ++ ) inv[i] = ( mod - mod / i ) * inv[mod % i] % mod;
    for( int i = 1 ; i < MAXN ; i ++ ) ifac[i] = ifac[i - 1] * inv[i] % mod;
    int t; scanf("%lld",&t);
    while( t -- ) solve();
    return 0;
}

::::