Divide and Sum (Codeforces 1444B)
Tags: Math, combinatorics

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) = \sum_{i = 1}^n |x_i - y_i|$$$.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 \leq n \leq 150\,000$$$).The second line contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_i \leq 10^9$$$) — elements of array $$$a$$$.

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

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$$$). 

Sample Inputs:
1
1 4

2
2 1 2 1

3
2 2 2 2 2 2

5
13 8 35 94 9284 34 54 69 123 846

Sample Outputs:
6

12

0

2588544

Solution (Python):
import os
import sys
input = sys.stdin.buffer.readline
import math
from collections import deque
from queue import PriorityQueue

class AC(object):

    def __init__(self):
        self.mod = 998244353
        n = int(input())
        a_list = list(map(int, input().split()))
        a_list.sort()
        ans = -sum(a_list[:n]) + sum(a_list[n:])
        ans %= self.mod
        self.init_combination_mod(self.mod, int(300000.0 + 1))
        ans *= self.cal_combination_mod(2 * n - 1, n - 1) * 2
        ans %= self.mod
        print(ans)

    def get_inv_mod(self, a, mod):
        return pow(a, mod - 2, mod)

    def init_combination_mod(self, mod, maxn=int(1000000.0)):
        self.factorial_mod = [1]
        self.mod = mod
        for i in range(1, maxn):
            self.factorial_mod.append(self.factorial_mod[-1] * i % self.mod)

    def cal_combination_mod(self, x, y):
        return self.factorial_mod[x] * self.get_inv_mod(self.factorial_mod[x - y], self.mod) % self.mod * self.get_inv_mod(self.factorial_mod[y], self.mod) % self.mod
if __name__ == '__main__':
    ac = AC()
''

Solution (Python):
(N, MOD) = (300005, 998244353)
f = [1] * N
for i in range(1, N):
    f[i] = f[i - 1] * i % MOD
n = int(input())
ar = sorted(list(map(int, input().split())))
e = (-sum(ar[:n]) + sum(ar[-n:])) % MOD
e = e * f[2 * n] % MOD
e = e * pow(f[n], MOD - 2, MOD) % MOD
e = e * pow(f[n], MOD - 2, MOD) % MOD
print(e)

Solution (Python):
m = 998244353
n = int(input())
l = sorted(map(int, input().split()))
N = 2 * n
t = 1
a = (sum(l[n:]) - sum(l[:n])) % m
for i in range(n):
    a = a * (N - i) % m
for i in range(1, n + 1):
    t = t * i % m
print(pow(t, m - 2, m) * a % m)