Codeforces 1445D. Divide and Sum（组合数学）

60 阅读 0 评论 40 点赞

我是靠谱客的博主自由钢笔，最近开发中收集的这篇文章主要介绍Codeforces 1445D. Divide and Sum（组合数学），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

You are given an array ???? of length 2????. Consider a partition of array ???? into two subsequences ???? and ???? of length ???? each (each element of array ???? should be in exactly one subsequence: either in ???? or in ????).

Let’s sort ???? in non-decreasing order, and ???? in non-increasing order, we can denote the sorted versions by ???? and ????, respectively. Then the cost of a partition is defined as ????(????,????)=∑????????=1|????????−????????|.

Find the sum of ????(????,????) over all correct partitions of array ????. Since the answer might be too big, print its remainder modulo 998244353.

Input
The first line contains a single integer ???? (1≤????≤150000).

The second line contains 2???? integers ????1,????2,…,????2???? (1≤????????≤109) — elements of array ????.

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

Examples
inputCopy
1
1 4
outputCopy
6
inputCopy
2
2 1 2 1
outputCopy
12
inputCopy
3
2 2 2 2 2 2
outputCopy
0
inputCopy
5
13 8 35 94 9284 34 54 69 123 846
outputCopy
2588544
Note
Two partitions of an array are considered different if the sets of indices of elements included in the subsequence ???? are different.

In the first example, there are two correct partitions of the array ????:

????=[1], ????=[4], then ????=[1], ????=[4], ????(????,????)=|1−4|=3;
????=[4], ????=[1], then ????=[4], ????=[1], ????(????,????)=|4−1|=3.
In the second example, there are six valid partitions of the array ????:

????=[2,1], ????=[2,1] (elements with indices 1 and 2 in the original array are selected in the subsequence ????);
????=[2,2], ????=[1,1];
????=[2,1], ????=[1,2] (elements with indices 1 and 4 are selected in the subsequence ????);
????=[1,2], ????=[2,1];
????=[1,1], ????=[2,2];
????=[2,1], ????=[2,1] (elements with indices 3 and 4 are selected in the subsequence ????).

题意：
$2 n$ 个数，取 $n$ 个顺序排，其他 $n$ 个逆序排，然后两组数依次相减取绝对值，结果相加。求所有可能的结果的和。

思路：
将这 $2 n$ 个数排序，则无论怎么选，都是后面 $n$ 个数减去前面 $n$ 个数，所以可以将后面 $n$ 个数当正数，前面 $n$ 个数当负数，一共有 $C (2 n, n)$ 种选法。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <string>

using namespace std;

typedef long long ll;

const int mod = 998244353 ;
const int maxn = 1e6 + 7;

ll fac[maxn],inv[maxn];

ll qpow(ll a,ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b = b >> 1;
    }
    return res % mod;
}

ll C(ll n,ll m)
{
    if(m > n || m < 0)
        return 0;
    return fac[n] * ((inv[n - m] * inv[m]) % mod) % mod;
}

void init()
{
    fac[0] = 1;
    inv[0] = 1;
    for(int i = 1;i <= maxn - 2;i++)
    {
        fac[i] = (fac[i - 1] * i) % mod;
        inv[i] = qpow(fac[i],mod - 2);
    }
}

int a[maxn];
int main() {
    init();
    int n;scanf("%d",&n);
    for(int i = 1;i <= 2 * n;i++) {
        scanf("%d",&a[i]);
    }
    sort(a + 1,a + 1 + 2 * n);
    
    ll num = C(2 * n,n);
    ll ans = 0;
    
    for(int i = n + 1;i <= 2 * n;i++) {
        ans += num % mod * a[i] % mod;
        ans %= mod;
    }
    for(int i = 1;i <= n;i++) {
        ans -= num % mod * a[i] % mod;
        ans = (ans % mod + mod) % mod;
    }
    printf("%lldn",ans % mod);
    return 0;
}