Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad)-D. Divide and Sum

本文主要是介绍Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad)-D. Divide and Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

You are given an array a of length 2n. Consider a partition of array a into two subsequences p and q of length n each (each element of array a should be in exactly one subsequence: either in p or in q).

Let’s sort p in non-decreasing order, and q in non-increasing order, we can denote the sorted versions by x and y, respectively. Then the cost of a partition is defined as f(p,q)=∑ni=1|xi−yi|.

Find the sum of f(p,q) over all correct partitions of array a. Since the answer might be too big, print its remainder modulo 998244353.

Input
The first line contains a single integer n (1≤n≤150000).

The second line contains 2n integers a1,a2,…,a2n (1≤ai≤109) — elements of array a.

Output
Print one integer — the answer to the problem, modulo 998244353.

Examples
input
1
1 4
output
6
input
2
2 1 2 1
output
12
input
3
2 2 2 2 2 2
output
0
input
5
13 8 35 94 9284 34 54 69 123 846
output
2588544
Note
Two partitions of an array are considered different if the sets of indices of elements included in the subsequence p are different.

In the first example, there are two correct partitions of the array a:

p=[1], q=[4], then x=[1], y=[4], f(p,q)=|1−4|=3;
p=[4], q=[1], then x=[4], y=[1], f(p,q)=|4−1|=3.
In the second example, there are six valid partitions of the array a:

p=[2,1], q=[2,1] (elements with indices 1 and 2 in the original array are selected in the subsequence p);
p=[2,2], q=[1,1];
p=[2,1], q=[1,2] (elements with indices 1 and 4 are selected in the subsequence p);
p=[1,2], q=[2,1];
p=[1,1], q=[2,2];
p=[2,1], q=[2,1] (elements with indices 3 and 4 are selected in the subsequence p).

题意：给定一个长度为2*n的数组a，将a分成两份放在p数组和q数组里，p和q的长度相同，且里面的元素都来自a数组并且在a数组里一一对应，p非降序排列成数组x，q非升序排列为y，
我们设 $f(p,q)=\sum_{i=1}^n|x_i-y_i|$ ,求所有不重复排列的 $f (p, q)$ 的和，结果模998244353取余

思路：这题完全就是一个排序求和然后求排列组合就行了，我们可以先将a数组排序，然后去分成两个数组，假设 $n = 2$ ,同时 $a_1,a_2,a_3,a_3$ 升序排列，则所有 $f (p, q)$ 的和可以计算出结果为 $C_{2*n}^n*(a_4+a_3-a_2-a_1)$ ,算到这里就已经差不多了，排序求前半段和后半段的和然后做差，再求排列组合，相乘即可，我再做差这个地方错了两次，因为前面取模可能导致总和小于数组一半的和，所以在这个地方最好是先加上MOD，再做差，然后再取模

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD=998244353;
const ll N=2e5+5;
const ll INF=0x3f3f3f;
ll V[N];
void init()
{V[1]=1;for(int i=2;i<N;i++)V[i]=V[i-1]*2%MOD;
}
ll mod_pow(ll x, ll n, ll p){ll res = 1;while(n){if(n & 1) res =res * x % p;x = x * x % p;n >>= 1;}return res;
}ll comb(ll n, ll m, ll p){if(m > n) return 0;ll ret = 1;m = min(n - m, m);for(int i = 1; i <= m; i ++){ll a = (n + i - m) % p;ll b = i % p;ret = ret * (a * mod_pow(b, p - 2, p) % p) % p;}return ret;
}ll Lucas(ll n, ll m, ll p){//从n中选m个取模;if(m == 0) return 1;return comb(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}ll Mpow(ll a,ll b){ll r=1,base=a;while(b){if(b&1) r*=base;base*=base;b>>=1;}return r;
}void slove()
{ll n;cin>>n;n*=2;ll a[n+5];ll sum=0;for(ll i=0;i<n;i++){cin>>a[i];sum+=a[i];sum%=MOD;}sort(a,a+n);ll sum1=0;for(ll i=0;i<n/2;i++){sum1+=a[i];sum1%=MOD;}sum=sum+MOD-sum1;sum%=MOD;sum=sum+MOD-sum1;sum%=MOD;ll ans=((Lucas(n,n/2,MOD)%MOD)*sum)%MOD;cout<<ans%MOD<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//init();//int t;cin>>t;//while(t--)slove();return 0;
}