Description
给定一个长度为 (2n) 的序列,你需要把它分成两个长度都是 (n) 的子序列,两部分分别以降序和升序排列,定义一种方案的权值为 (sum_i |x_i - y_i|),求所有方案的权值的和。
Solution
将绝对值视为差的形式,那么无论如何划分,权值都是较大的 (n) 个数的和减去较小的 (n) 个数的和。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
const int mod = 998244353;
int n, a[N], ans;
int qpow(int p, int q)
{
return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
}
int inv(int p)
{
return qpow(p, mod - 2);
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n + n; i++)
cin >> a[i];
sort(a + 1, a + n + n + 1);
for (int i = 1; i <= n; i++)
ans -= a[i];
for (int i = n + 1; i <= n + n; i++)
ans += a[i];
ans %= mod;
for (int i = 1; i <= n; i++)
ans = ans * (n + i) % mod;
for (int i = 1; i <= n; i++)
ans = ans * inv(i) % mod;
cout << ans << endl;
return 0;
}