D. Divide and Sum (组合数、思维)

添加链接描述

对于任意分组可以发现其实差值是一样的，将绝对值拆开，会发现都是后面n个大的-前面n的小的。

看例子 a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 （已按大小排序）

假设对于第一组 取了前面3个，后面2个，然后其从很小到大排序，后面一组只可能是取前面2个，后面3个，从大到小排序。那么对于第一组的前3个（顺序）与后面一组的前3个（逆序），必然是第一组的前三个都是a，后面一组的前三个都是b,然后对于第一组后两个，和后一组后两个，第一组后两个必然是b,后一组后两个必然是a。将绝对值去掉一组的差值就等于b1+b2+b3+b4+b5-a1-a2-a3-a4-a5，所有情况都是如此，将上例3化为k,2化为n-k就是普遍情况。然后总共有从2n个取出n个的情况，相乘即可。

#include<iostream>
#include<algorithm>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;
ll lst[Max];
ll Mod = 998244353;
ll f[Max];
ll qpow(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = ans * base % Mod;
base = base * base % Mod;
b >>= 1;
}
return ans;
}
void init() {
f[0] = 1;
for (int i = 1;i <= 1e6;i++) {
f[i] = f[i - 1] * i % Mod;
}
}
ll cal(ll n, ll m) {
if (n < m) return 0;
return 1ll * f[n] * qpow(f[m], Mod - 2) % Mod * qpow(f[n - m], Mod - 2) % Mod;
}
int main()
{
ll n;cin >> n;
init();
for (int i = 1;i <= 2*n;i++)cin >> lst[i];
ll ans = 0;
sort(lst + 1, lst + 1 + 2*n);
for (int i = 1;i <= n;i++)
{
ans += lst[2 * n - i + 1] - lst[i];
}
ans = (ans % Mod * cal(n * 2, n)) % Mod;
cout << ans << endl;
}

最后

以上就是大意绿草为你收集整理的D. Divide and Sum (组合数、思维)的全部内容，希望文章能够帮你解决D. Divide and Sum (组合数、思维)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。