[CF1444B] Divide and Sum - 结论,组合数学

Description

给定一个长度为 \(2n\) 的序列，你需要把它分成两个长度都是 \(n\) 的子序列，两部分分别以降序和升序排列，定义一种方案的权值为 \(\sum_i |x_i - y_i|\)，求所有方案的权值的和。

Solution

将绝对值视为差的形式，那么无论如何划分，权值都是较大的 \(n\) 个数的和减去较小的 \(n\) 个数的和。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;
const int mod = 998244353;

int n, a[N], ans;

int qpow(int p, int q)
{
    return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
}

int inv(int p)
{
    return qpow(p, mod - 2);
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n + n; i++)
        cin >> a[i];

    sort(a + 1, a + n + n + 1);

    for (int i = 1; i <= n; i++)
        ans -= a[i];
    for (int i = n + 1; i <= n + n; i++)
        ans += a[i];

    ans %= mod;
    
    for (int i = 1; i <= n; i++)
        ans = ans * (n + i) % mod;
    for (int i = 1; i <= n; i++)
        ans = ans * inv(i) % mod;

    cout << ans << endl;
    return 0;
}

[CF1444B] Divide and Sum - 结论,组合数学

原文：https://www.cnblogs.com/mollnn/p/13925639.html