概述
题意：
给定一个长度为2n的数组，将数组分成两个长度为n的数组p,q，将p从小到大排序，将q从大到小排序，对于每种分法，f(p,q)= ∑ i = 1 n sum_{i=1}^{n} ∑i=1n|xi−yi|.求总和
题目：
You are given an array a of length 2n. Consider a partition of array a into two subsequences p and q of length n each (each element of array a should be in exactly one subsequence: either in p or in q).
Let’s sort p in non-decreasing order, and q in non-increasing order, we can denote the sorted versions by x and y, respectively. Then the cost of a partition is defined as f(p,q)= ∑ i = 1 n sum_{i=1}^{n} ∑i=1n|xi−yi|
Find the sum of f(p,q) over all correct partitions of array a. Since the answer might be too big, print its remainder modulo 998244353.
Input
The first line contains a single integer n (1≤n≤150000).
The second line contains 2n integers a1,a2,…,a2n (1≤ai≤109) — elements of array a.
Output
Print one integer — the answer to the problem, modulo 998244353.
Examples
Input
1
1 4
Output
6
Input
2
2 1 2 1
Output
12
Input
3
2 2 2 2 2 2
Output
0
Input
5
13 8 35 94 9284 34 54 69 123 846
Output
2588544
Note
Two partitions of an array are considered different if the sets of indices of elements included in the subsequence p are different.
In the first example, there are two correct partitions of the array a:
p=[1], q=[4], then 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.
In the second example, there are six valid partitions of the array a:
p=[2,1], q=[2,1] (elements with indices 1 and 2 in the original array are selected in the subsequence p);
p=[2,2], q=[1,1];
p=[2,1], q=[1,2] (elements with indices 1 and 4 are selected in the subsequence p);
p=[1,2], q=[2,1];
p=[1,1], q=[2,2];
p=[2,1], q=[2,1] (elements with indices 3 and 4 are selected in the subsequence p).
分析：
1.考虑将a先从小到大排序后，可以分成前后两块,其中因为p，q的长度是固定的n。
2.求和是每个对应值差的绝对值。可以看作任意两个值交换集合，因为得到差值的绝对值相同，这里顺序对结果没有影响。
3.前面对a排序，所以对于每种方案，一定是右块的数去减左块的数，其值和为ans；
4.而所有的排列总数是
C
m
n
C_{m}^{n}
Cmn（m=2*n），所以总的答案ans=ans
×
C
m
n
times C_{m}^{n}
×Cmn
5.由于是大数需要求余，
C
m
n
C_{m}^{n}
Cmn=
m
!
n
!
(
m
−
n
)
!
frac{m!}{n!(m-n)!}
n!(m−n)!m!,只需拆开来算时求
n
！
×
n！times
n！×
(
m
−
n
)
!
(m-n)!
(m−n)!的逆元即可，又n==m-n,只需求
n
!
n!
n!的逆元即可，即根据费马小定理和快速幂求
n
!
m
o
d
−
2
n!^{mod-2}
n!mod−2.
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
typedef long long ll;
const int M=3e5+5;
int n,m;
ll ans,num,a,b,dp[M];
ll dfs(ll x,int y){
ll ans=1;
while(y){
if(y&1) ans=ans*x%mod;
y>>=1;
x=x*x%mod;
}
return ans;
}
int main(){
cin>>n;
m=n<<1;
for(int i=0;i<m;i++)
cin>>dp[i];
sort(dp,dp+m);
for(int i=0;i<n;i++)
ans=(ans+dp[n+i]-dp[i])%mod;
a=b=1;
for(int i=2;i<=m;i++){
b=b*i%mod;
if(i==n)
a=b;
}
num=dfs(a,mod-2);
ans=ans*b%mod*num%mod*num%mod;
cout<<ans<<endl;
return 0;
}
最后
以上就是平淡歌曲为你收集整理的Divide and Sum CodeForces - 1445D（排列组合+逆元）题意：题目：分析：AC代码：的全部内容，希望文章能够帮你解决Divide and Sum CodeForces - 1445D（排列组合+逆元）题意：题目：分析：AC代码：所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复