题意：
给定一个长度为2n的数组，将数组分成两个长度为n的数组p,q，将p从小到大排序，将q从大到小排序，对于每种分法，f(p,q)=∑i=1n\sum_{i=1}^{n}∑i=1n|xi−yi|.求总和
题目：
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)=∑i=1n\sum_{i=1}^{n}∑i=1n|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).
分析：
1.考虑将a先从小到大排序后，可以分成前后两块,其中因为p，q的长度是固定的n。
2.求和是每个对应值差的绝对值。可以看作任意两个值交换集合，因为得到差值的绝对值相同，这里顺序对结果没有影响。
3.前面对a排序，所以对于每种方案，一定是右块的数去减左块的数，其值和为ans；
4.而所有的排列总数是CmnC_{m}^{n}Cmn（m=2*n），所以总的答案ans=ans ×Cmn\times C_{m}^{n}×Cmn
5.由于是大数需要求余，CmnC_{m}^{n}Cmn=m!n!(m−n)!\frac{m!}{n!(m-n)!}n!(m−n)!m!,只需拆开来算时求n！×n！\timesn！×(m−n)!(m-n)!(m−n)!的逆元即可，又n==m-n,只需求 n!n!n!的逆元即可，即根据费马小定理和快速幂求n!mod−2n!^{mod-2}n!mod−2.
AC代码：
#include<bits/stdc++.h>using namespace std;#define mod 998244353typedef long long ll;const int M=3e5+5;int n,m;ll ans,num,a,b,dp[M];ll dfs(ll x,int y){ll ans=1;while(y){if(y&1) ans=ans*x%mod;y>>=1;x=x*x%mod;}return ans;}int main(){cin>>n;m=n<<1;for(int i=0;i<m;i++)cin>>dp[i];sort(dp,dp+m);for(int i=0;i<n;i++)ans=(ans+dp[n+i]-dp[i])%mod;a=b=1;for(int i=2;i<=m;i++){b=b*i%mod;if(i==n)a=b;}num=dfs(a,mod-2);ans=ans*b%mod*num%mod*num%mod;cout<<ans<<endl;return 0;}
