Codeforces 1445D. Divide and Sum

題目大意

• 給一個 2 n 2n 2n的序列，將他們分成 p p p和 q q q兩個長為 n n n的序列，求所有情況下，將 p p p升序和將 q q q降序后的 ∑ i = 1 n ∣ p i ? q i ∣ \sum_{i=1}^n|p_i-q_i| ∑i=1n?∣pi??qi?∣之和，
• n ≤ 150000 n\leq150000 n≤150000

題解

• 考慮每兩個數的貢獻，將整個序列排序后，對半分成兩份，左半邊在 p p p中的數量和右半邊在 q q q中的數量一定會相同，左半邊在 q q q中的數量和左半邊在 p p p中的數量也一定相同， 那么只可能是左邊的 p p p和右邊的 q q q匹配，右邊的 q q q和左邊的 p p p匹配，
• 也就是說，整個序列無論怎么分，任意一種情況的貢獻都是大的一半減去小的一半，然后再乘上方案數 ( 2 ? n n ) \tbinom{2* n}{n} (n2?n?)即可，

代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 300010
#define ll long long
#define md 998244353
ll a[N], f[N];
ll ksm(ll x, ll y) {
	if(!y) return 1;
	ll l = ksm(x, y / 2);
	if(y % 2) return l * l % md * x % md;
	return l * l % md;
}
int main() {
	int n, i, j;
	scanf("%d", &n);
	for(i = 1; i <= 2 * n; i++) scanf("%lld", &a[i]);
	sort(a + 1, a + 2 * n + 1);
	ll ans = 0;
	for(i = 1; i <= n; i++) {
		ans = (ans + a[i + n] - a[i]) % md;
	}
	f[0] = 1;
	for(i = 1; i <= 2 * n; i++) f[i] = f[i - 1] * i % md;
	printf("%lld\n", ans * f[n * 2] % md * ksm(f[n], md - 2) % md * ksm(f[n], md - 2) % md);
	return 0;
}