CF1444B Divide and Sum

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

N/A

N/A

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 $ : 1. $ p = [1] $ , $ q = [4] $ , then $ x = [1] $ , $ y = [4] $ , $ f(p, q) = |1 - 4| = 3 $ ; 2. $ 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 $ : 1. $ p = [2, 1] $ , $ q = [2, 1] $ (elements with indices $ 1 $ and $ 2 $ in the original array are selected in the subsequence $ p $ ); 2. $ p = [2, 2] $ , $ q = [1, 1] $ ; 3. $ p = [2, 1] $ , $ q = [1, 2] $ (elements with indices $ 1 $ and $ 4 $ are selected in the subsequence $ p $ ); 4. $ p = [1, 2] $ , $ q = [2, 1] $ ; 5. $ p = [1, 1] $ , $ q = [2, 2] $ ; 6. $ p = [2, 1] $ , $ q = [2, 1] $ (elements with indices $ 3 $ and $ 4 $ are selected in the subsequence $ p $ ).