Problem - 1445D - Codeforces
题意:
给你一个长度为2n的数组a。考虑将数组a划分为两个子序列p和q，每个子序列的长度为n（数组a的每个元素应该正好在一个子序列中：要么在p中，要么在q中）。
让我们以非递减顺序对p进行排序，以非递增顺序对q进行排序，我们可以分别用x和y来表示排序后的版本。那么一个分区的成本被定义为f(p,q)=∑ni=1|xi-yi|。
求数组a所有正确分区的f(p,q)之和。由于答案可能太大，请打印其余数，即998244353。
输入
第一行包含一个整数n（1≤n≤150000）。
第二行包含2n个整数a1,a2,...,a2n（1≤ai≤109）--数组a的元素。
输出
打印一个整数 - 问题的答案，模数998244353。
例子
输入复制
1
1 4
outputCopy
6
输入副本
2
2 1 2 1
输出拷贝
12
输入复制
3
2 2 2 2 2 2
输出拷贝
0
输入复制
5
13 8 35 94 9284 34 54 69 123 846
输出拷贝
2588544
注意
如果一个数组的两个分区包含在子序列p中的元素索引集不同，则认为是不同的。
在第一个例子中，有两个正确的数组a的分区。
p=[1], q=[4], 那么x=[1], y=[4], f（p,q）=|1-4|=3;
p=[4], q=[1], then x=[4], y=[1], f(p,q)=|4-1|=3.
在第二个例子中，数组a有六个有效分区。
p=[2,1], q=[2,1]（原数组中指数为1和2的元素在子序列p中被选中）。
p=[2,2], q=[1,1];
p=[2,1], q=[1,2]（在子序列p中选择指数为1和4的元素）。
p=[1,2], q=[2,1];
p=[1,1], q=[2,2];
p=[2,1], q=[2,1]（指数为3和4的元素在子序列p中被选中）。
题解: 题意很简单,本题关键处在于能否看出构建出的序列得到的之都相等
我们列几个例子就可以发现
//1 2 3 4 5 6 //3 2 1 //4 5 6 9
//6 2 1 //3 4 5 9
只要是符合的结果肯定都一样
先排序一下计算,得出一个的成本
剩下的就是看有多少种情况即可,从2*n里去n个,答案很明显,组合数
#include<iostream>#include<algorithm>#include<map>#include<queue>#include<vector>#include<cstring>#include<stack>using namespace std;long long n;long long a[400000];long long fac[400000];long long infac[400000]; int mod = 998244353;long long qpow(long long a,long long x){long long ans = 1;while(x){if(x&1)ans = ans*a%mod;a = a*a%mod;x = x/2;}return ans;}void solve(){int n;cin >> n;for(int i = 1;i <= n*2;i++)cin >> a[i];sort(a+1,a+1+2*n);long long ans = 0;for(int i = 1;i <= n;i++){ans = (ans+a[i+n]-a[i]+mod)%mod;}infac[1] = 1;fac[1] = 1;for(int i = 2;i <= 2*n;i++){fac[i] = (fac[i-1]*i)%mod;infac[i] = infac[i-1]*qpow(i,mod-2)%mod;}cout<<ans*fac[2*n]%mod*infac[n]%mod*infac[n]%mod;}int main(){int t = 1;//cin >> t;while(t--){solve();}}//1 2 3 4 5 6//3 2 1//4 5 6 9//6 2 1//3 4 5 //c 5 2//a5 / a2 a3
