题解 34：P17762 「奶龙OI」Round 3 - 跑酷大神

liu鲤鱼 · 2026-10-24 18:42:27 · 题解

思路

不难发现，分成的这 n 个二元组，要让它们有交，则其所有组左端点的最大值必须小于右端点的最小值。如果不满足，则这种排列的代价为 0，不需要考虑。

也就是说，我们把原数组排一个序，在 1 至 n 的一定是作为左端点，n+1 至 2 \times n 的一定是右端点。此时可以发现，一个非 0 排列的代价即为排序后第 n+1 的值减去第 n 的值。

于是所有左端点排列的可能数就为 n!，右端点同理。则总的可能为 (n!)^2。

但是考虑左右端点可以互换。则每一对都可以交换，有两种可能。总共就是 2^n 种。

共计 (n!)^2 \times 2^n 种可行的排列。乘上第 n+1 和第 n 个的差既是最终答案。

代码

ll t,n,k,ans,jc[N],jc2[N],a[N];
bool flag;
int main(){
    t=read();
    jc[0]=jc2[0]=1;
    for(ll i=1;i<N/2;i++){
        jc[i]=jc[i-1]*i%mod;//预处理阶乘
        jc2[i]=jc2[i-1]*2%mod;//预处理 2 的幂
    }
    while(t--){
        n=read();
        ll ans=(jc[n]*jc[n])%mod*jc2[n]%mod;//可行的排列数
        for(ll i=1;i<=2*n;i++) a[i]=read();
        sort(a+1,a+n*2+1);
        ans=ans*(a[n+1]-a[n])%mod;//总代价
        write(ans);
        putchar('\n');
    }
    return 0;
}