题目链接
题意：
的给个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∗na[i]−∑i=1na[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
)
Cbinom{n}{2n}
C(2nn)种情况
那么最终答案就是：
C
(
n
2
n
)
∗
(
∑
i
=
n
+
1
2
∗
n
a
[
i
]
−
∑
i
=
1
n
a
[
i
]
)
Cbinom{n}{2n}*(sum_{i=n+1}^{2*n}{a[i]}-sum_{i=1}^{n}{a[i]})
C(2nn)∗(i=n+1∑2∗na[i]−i=1∑na[i])
#includeusing 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<
