还是期望大佬

· · 题解

初看有点难入手，但你发现总方案数是固定的，于是我们考虑算期望 E，那么答案就是 (n!)^2E。

首先，如果一个人的 P_i\le K 或 Q_i\le K，那么她一定在两个方案里都被选。我们设 r=\#\{i|P_i\le K,Q_i\le K\}，枚举 r，那么这部分会保证有 2K-r 个人在两个方案都被选，概率为：

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

这公式的含义是确定 P_i\le K 的 K 人后，从这 K 个中选 r 个，再从剩余的 N-K 个中选 K-r 个做 Q_i\le K 的人。

于是我们固定了 2K-r 个人都被选，要从剩余 N-2K+r 个人中再选出 2K-(2K-r)=r 个人。也就是说，除去 P_i\le K 或 Q_i\le K 的人后，剩下的人中 Q_i 前 r 小的在方法一被选，P_i 前 r 小的在方法二被选。于是对于方法一中被选的 r 个人，她在方法二中不被选的概率为：

1-\frac{r}{N-2K+r}=\frac{N-2K}{N-2K+r}

故这部分的期望：

\frac{(N-2K)}{N-2K+r}r

综上：

E=\sum\limits_{r=0}^K\frac{(N-2K)}{N-2K+r}r\frac{\binom{K}{r}\binom{N-K}{K-r}}{\binom{N}{K}}

于是答案为：

(N!)^2\sum\limits_{r=0}^K\frac{(N-2K)}{N-2K+r}r\frac{\binom{K}{r}\binom{N-K}{K-r}}{\binom{N}{K}}

可以 O(N) 计算。

贴代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000010,mod=998244353;
int T,jc[N],inv[N],n,k,ans;
int C(int x,int y){return jc[x]*inv[y]%mod*inv[x-y]%mod;}
void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
int ksm(int x,int k){
    int ans=1;
    while(k){
        if(k&1)ans=ans*x%mod;
        x=x*x%mod,k>>=1; 
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    jc[0]=jc[1]=inv[0]=inv[1]=1;
    for(int i=2;i<N;i++)jc[i]=jc[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<N;i++)inv[i]=inv[i-1]*inv[i]%mod;
    cin>>T;
    while(T--){
        cin>>n>>k,ans=0;
        for(int r=0;r<=k;r++)
            add(ans,C(k,r)*C(n-k,k-r)%mod*ksm(C(n,k),mod-2)%mod*r%mod*(n-2*k)%mod*ksm(n-2*k+r,mod-2)%mod);
        cout<<ans*jc[n]%mod*jc[n]%mod<<'\n';
    }
    return 0;
}