题目链接
题意：
的给个2*n长度的数组，将其划分为两个长度为n的数组分别给p和q，要求满足p为不上升序列，q为不下降序列。
定义一个函数
f
(
p
,
q
)
=
∑
i
=
1
n
∣
x
i
?
y
i
∣
f(p,q)=\sum_{i=1}^{n}|x_i-y_i|
f(p,q)=∑i=1n?∣xi??yi?∣;
计算所有
f
f
f的和，并对998244353 去模。
题解：
是个结论题。所2n的数进行排序，得到一个新的序列，记为数组a。
可以发现按照上面的顺序随意取n个数给p，然后剩下的数全给q，就构造出了这样的序列。
然后就是求f的问题。这里就是一个结论了：
对于任意的
f
=
∑
i
=
n
+
1
2
?
n
a
[
i
]
?
∑
i
=
1
n
a
[
i
]
f=\sum_{i=n+1}^{2*n}{a[i]}-\sum_{i=1}^{n}{a[i]}
f=∑i=n+12?n?a[i]?∑i=1n?a[i]
这个结论可以自己写个样例试着弄一下，就能发现这个结论的正确性。
是因为加了绝对值后，若要把绝对值符号去掉，那就要把大的数减去小的数。
那么对于任意一个
∣
x
i
?
y
i
∣
|x_i-y_i|
∣xi??yi?∣，若去掉绝对值，一定是
m
a
x
(
x
i
,
y
i
)
?
m
i
n
(
x
i
,
y
i
)
max(x_i,y_i)-min(x_i,y_i)
max(xi?,yi?)?min(xi?,yi?)
那么由于
f
(
p
,
q
)
=
∑
i
=
1
n
∣
x
i
?
y
i
∣
f(p,q)=\sum_{i=1}^{n}|x_i-y_i|
f(p,q)=∑i=1n?∣xi??yi?∣绝对值去掉后，一定是所有大的数-所有小的数，那么就是所有最大的n个数，减去最小的n个数。然后这样的数可以取
C
(
n
2
n
)
C\binom{n}{2n}
C(2nn?)种情况
那么最终答案就是：
C
(
n
2
n
)
?
(
∑
i
=
n
+
1
2
?
n
a
[
i
]
?
∑
i
=
1
n
a
[
i
]
)
C\binom{n}{2n}*(\sum_{i=n+1}^{2*n}{a[i]}-\sum_{i=1}^{n}{a[i]})
C(2nn?)?(i=n+1∑2?n?a[i]?i=1∑n?a[i])
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=300005;
const int mod=998244353;
int n,m;
int a[maxn];
LL qpow(LL a,LL k){
LL res=1;
while(k){
if(k&1) res=res*a%mod;
k>>=1;
a=a*a%mod;
}
return res;
}
void solve(){
cin>>n;m=2*n;
for(int i=1;i<=2*n;i++) cin>>a[i];
sort(a+1,a+m+1);
LL ans=0;
for(int i=1;i<=n;i++)ans=(ans-a[i])%mod;
for(int i=n+1;i<=m;i++) ans=(ans+a[i])%mod;
for(int i=n+1;i<=m;i++) ans=ans*i%mod;
for(int i=1;i<=n;i++) ans=ans*qpow(i,mod-2)%mod;
ans=(ans%mod+mod)%mod;
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;t=1;
while(t--) solve();
return 0;
}
