Divide and Sum (Codeforces 1445D)
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):
def res(n):
    nu = s = 1
    for i in range(n):
        nu = nu * (2 * n - i) % m
        s = s * (i + 1) % m
    return nu * pow(s, m - 2, m) % m
m = 998244353
n = int(input())
fg = sorted(list(map(int, input().split())))
f = abs(sum(fg[:n]) - sum(fg[n:]))
print(f * res(n) % m)

Solution (Python):
def ncr(n, r, p):
    num = 1
    den = 1
    for i in range(r):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    return num * pow(den, p - 2, p) % p

def solve(n, a):
    a.sort()
    M = 998244353
    ss = sum(a[:n])
    ls = sum(a[n:])
    return (ls - ss) * ncr(2 * n, n, M) % M
n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

Solution (Python):
import queue
from math import inf, gcd, floor, sqrt, ceil, log, log2, log10, factorial
import sys
from collections import *
from random import *
import itertools
sys.setrecursionlimit(99999)
eps = sys.float_info.epsilon
P = 2
INF = 1000000000.0 + 1
MOD = 998244353

def is_prime(n):
    if n == 0 or n == 1:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

def div_up(n, k):
    if n % k == 0:
        return n // k
    else:
        return n // k + 1

def num_len(n, base=10):
    if n == 0:
        return 1
    return int(floor(log(n, base) + 1))

def down(a):
    for i in range(1, len(a)):
        if a[i] > a[i - 1]:
            return False
    return True

def up(a):
    for i in range(1, len(a)):
        if a[i] < a[i - 1]:
            return False
    return True

def code(c):
    return ord(c) - 32

def _hash_(s):
    (res, p) = (0, 1)
    for i in range(len(s)):
        res += code(s[i]) * p
        res %= MOD
        p *= P
        p %= MOD
    return res % MOD

def remove_edge(v, u, graph):
    graph[v].remove(u)
    graph[u].remove(v)

def all_eq(a):
    for i in range(len(a) - 1):
        if a[i] != a[i + 1]:
            return False
    return True

def kmp(s, pr):
    n = len(s)
    pr[0] = 0
    for i in range(1, n):
        j = pr[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pr[j - 1]
        if s[i] == s[j]:
            j += 1
        pr[i] = j

def lcm(a, b):
    return a * b // gcd(a, b)

def gcd_advanced(a, b):
    if a == 0:
        return (0, 1, b)
    (x1, y1, g) = gcd_advanced(b % a, a)
    return (y1 - x1 * (b // a), x1, g)

def ok(a, m):
    pref = [False for i in range(m)]
    suf = [False for i in range(m)]
    pref[0] = True
    suf[m - 1] = True
    for i in range(1, m):
        if a[i] > a[i - 1] and pref[i - 1]:
            pref[i] = True
    for i in range(m - 2, -1, -1):
        if a[i] < a[i + 1] and suf[i + 1]:
            suf[i] = True
    for i in range(1, m - 1):
        if pref[i - 1] and suf[i + 1]:
            return True
    return False

def zeros(n):
    res = 0
    while n > 0:
        if n % 2 == 0:
            res += 1
        n >>= 1
    return res

def ones(n):
    res = 0
    while n > 0:
        res += n & 1
        n >>= 1
    return res

def len2(n):
    res = 0
    while n > 0:
        res += 1
        n >>= 1
    return res

def r1(n):
    x = n - 2
    if n % 4 == 3 and len2(x) % 2 != zeros(x) % 2:
        return True
    return False

def r2(n):
    x = n + 1
    if n % 2 == 0 and len2(x) % 2 == zeros(x) % 2:
        return True
    return False

def r3(n):
    x = n + 2
    if n % 4 == 1 and len2(x) % 2 != zeros(x) % 2:
        return True
    return False

def r4(n):
    x = n - 1
    if n % 2 == 1 and ones(x) % 2 == 0:
        return True
    return False

def power2(x):
    if ones(x) == 1:
        return True
    return False

def r0(n):
    if n % 3 == 0 and power2(n // 3):
        return True
    return False

def r5(n):
    x = n + 4
    if n % 8 == 2 and len2(x) % 2 != zeros(x) % 2:
        return True
    return False

def r6(n):
    x = n - 4
    if n % 8 == 6 and len2(x) % 2 != zeros(x) % 2:
        return True
    return False

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    res = 0
    for i in range(n):
        res += a[2 * n - i - 1] - a[i]
    fac_2n = fac_n = 1
    for i in range(2, n + 1):
        fac_n = fac_n * i % MOD
    for i in range(2, 2 * n + 1):
        fac_2n = fac_2n * i % MOD
    x = fac_2n * pow(fac_n ** 2, -1, MOD)
    print(x * res % MOD)
solve()

def debug():
    pass