D. Divide and Sum

题意

给2n长的序列a，将其划分成两个长度为n的子序列p， q，将p序列从小到大排序，其中第i个数值为xi，q序列从大到小排序，其中第i个数值为yi。

定义​

计算所有划分的f(p, q)的和，mod 998244353。

思路

将有2n个数的a序列进行排序，通过观察我们可以发现对于两个数下标i，j都小于等于n/2或者都大于n/2，若ai和aj不在同一个序列，那么ai和aj在两个序列中的对应位置一定不相同。

证明：

不妨设i在序列p中，并且左边有numl个数比ai小，右边有numr个数比ai大，numl + numr = n - 1；
​
若ai与aj对应位置相同，并且aj在序列q中，那么左边有numl个数比aj大，右边有numr个数比aj小；
由于一个数要么在p序列中，要么在q序列中，那么不管ai与aj谁大谁小，大小在ai和aj之间的数都有numl + numr = n - 1个；
那么i和j一定不同时<=n/2或者> n/2
​
并且可以发现，i和j在a序列中的坐标一定相差n

由于加了绝对值，所以我们不管小的在p序列还是大的在p序列，都可以大减小，一个划分f(p, q)的值就为排序后的序列a后一半元素值的和减去前一半元素值的和，一共就有​个f(p, q)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 2e5 + 10;
ll qpow(ll base, ll n){ll ans = 1; while (n){if (n & 1) ans = ans * base % mod; base = base * base % mod; n >>= 1;} return ans;}
ll a[N << 1];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= 2 * n; ++ i) {
scanf("%lld", &a[i]);
}
sort(a + 1, a + 1 + 2 * n);
ll ans = 0;
ll x = 1;
for (int i = 1; i <= n; ++ i) {
ans += a[i + n] - a[i];
x = x * i % mod;
}
ans = ans % mod;
ll inv = qpow(x, mod - 2);
for (int i = 1; i <= n; ++ i) {
ans = ans * (i + n) % mod;
}
ans = ans * inv % mod;
printf("%lldn", ans);
return 0;
}

最后

以上就是阔达溪流为你收集整理的CodeForces 1445 - D. Divide and Sum - 思维 + 组合数（详解）D. Divide and Sum的全部内容，希望文章能够帮你解决CodeForces 1445 - D. Divide and Sum - 思维 + 组合数（详解）D. Divide and Sum所遇到的程序开发问题。

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