Problem - 1444B - B. Divide and Sum(组合数学+思维)

题目大意:给你一个长度为$2n$的序列$a$,你将它们平均分成两组,对第一组做不递减排序,得到序列$x$,第二组做不递增排序,得到序列$y$,求对于所有的序列$x,y$${\sum }_1^n|x_i?y_i|$.

解题思路:这个题可以打表,也可以分析,打表的话会发现,将序列$a$进行排序后,前$n$项只会与后$n$项进行运算,用一个整体的思想,这样的贡献值就是后$n$项的和减去前$n$项的和,然后乘以排列的个数就是答案.
分析一下这个题,我们这样思考,我们如果从前$n$个元素中取走了一个作为$y$序列中的元素,根据排序规则,它一定是从后向前来进行排序,而同样对应的元素在序列$x$中也是从后向前来排序,那么根据这种排序规则,一定是前$n$项去对应后$n$项.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int N = 3e5+5;
ll val[N];
const int mod = 998244353;
const int maxn = 3e5+5;
ll a[maxn];//a取到n最大
ll Pow(ll a,ll b){
    a%=mod;ll ans = 1;while(b){
    if(b&1)ans = (ans*a)%mod;a = (a*a)%mod;b/=2;}return ans%mod;
}
ll Quk(ll a,ll b){
    a%=mod;ll ans = 0;while(b){
    if(b&1)ans = (ans+a)%mod;a = (a+a)%mod;b/=2;}return ans%mod;
}
ll C(ll n,ll m){
    return Quk(Quk(a[n],Pow(a[n-m],mod-2)),Pow(a[m],mod-2))%mod;
}
ll A(ll n,ll m){
    return Quk(a[n],Pow(a[n-m],mod-2))%mod;
}
void initial(){
    a[0]=a[1]=1;for(ll i=2;i<maxn ;i++)a[i]=Quk(a[i-1],i);
}
int main(){
    syncfalse#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifinitial();int n;cin>>n;for (int i = 1; i <= n*2; ++i)cin>>val[i];sort(val+1, val+1+n*2);ll ans = 0;for (int i = n+1; i <= n*2; ++i){
    ans=(ans+val[i])%mod;}for (int i = 1; i <= n; ++i){
    ans=(ans-val[i]+mod)%mod;}cout << ans*C(2*n, n)%mod << "\n";return 0;
}