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;
}