题解 CF1444B 【Divide and Sum】

Zenith_Yeh · 2020-11-03 01:31:25 · 题解

很多同学都是通过手玩或打表找规律得到的。

规律是：结果是数列 a 中的大的 n 个数之和 - 小的 n 个数之和的 C_{2n}^{n} 倍。

为什么呢？

我们来证一下：

设数列 a 非降序排序后，前 n 个数分别为 \{u_1,u_2,u_3,\cdot\cdot\cdot,u_n\}，后 n 个数分别为 \{v_1,v_2,v_3,\cdot\cdot\cdot,v_n\}，那我们设 i 为前 n 个数被分配到数列 p 中的个数。

因为 p 为非递减且 q 为非递增，所以 p=\{\underbrace{u,u,u,\cdot\cdot\cdot,u}_{i\text{ 个}}\,,\underbrace{v,v,v,\cdot\cdot\cdot,v}_{n-i\text{ 个}}\},q=\{\underbrace{v,v,v,\cdot\cdot\cdot,v}_{i\text{ 个}}\,,\underbrace{u,u,u,\cdot\cdot\cdot,u}_{n-i\text{ 个}}\}。

所以 \sum_{i=1}^{n}|p_i-q_i|=\sum_{i=1}^{n}|u_i-v_i|=\sum_{i=1}^{n}(v_i-u_i)。

由于 \sum_{i=1}^{n}(v_i-u_i) 为确定的，所以只要求有多少个 f(p,q) 即可，不难发现为 C_{2n}^{n} 个。

所以答案为数列 a 中的大的 n 个数之和 - 小的 n 个数之和的 C_{2n}^{n} 倍。

上菜:

#include<bits/stdc++.h>
#define int long long//不开long long见祖宗
#define mod 998244353
using namespace std;
int n,a[150000*2+5],f[150000*2+5],inv[150000*2+5],ans;
int ksm(int x,int y)//由于要用到逆元求组合数，所以要快速幂
{   int res=1;
    while(y)
    {   if(y&1)res=x*res%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
signed main()
{   cin>>n;
    for(register int i=1;i<=2*n;++i)cin>>a[i];
    sort(a+1,a+n+n+1);//排序
    f[0]=1;
    for(register int i=1;i<=2*n;++i)//求逆元
    {   f[i]=f[i-1]*i%mod;
        inv[i]=ksm(f[i],mod-2);
    }
    for(register int i=2*n;i>=1;--i)//计算答案
    {   if(i<=n)ans=(ans+mod-f[2*n]*inv[n]%mod*inv[n]%mod*a[i]%mod)%mod;//若为小的n个数，则减
        else ans=(ans+f[2*n]*inv[n]%mod*inv[n]%mod*a[i]%mod)%mod;//若为大的n个数，则加
    }
    cout<<ans;
    return 0;
}