codeforces-#680-D

十一月 05, 2020

组合数学

D. Divide and Sum

题意

给出一个长度为2n的数组A

要求从中选出一个长度为n的子序列重新排序变为一个非降序的数组p

剩下n个数则重新排列变为一个非升序的数组q

定义这对(p,q)有一个花费为$f(p,q)=∑_{i=1}^n|p_i-q_i|$

求出这个长度为2n的数组中能产生的所有 (p,q)的花费和 mod 998244353

题解

首先题目要求从2n个数中找出n个数重新排序得到一个非降序的数组p和一个非升序的数组q

于是干脆给原数组A排序再讨论

现在假定A数组已经升序排列

现在从A数组中取出一个数作为$p_i$

那么由于p是非递减数列那么$p_{i+1}$~ $p_n$ 一定在$p_i$的右侧

同时取出一个数作为$q_i$

那么由于q是非递增数列那么$q_{i+1}$~ $p_n$ 一定在$p_i$的左侧

有一种比较直观的感受是若$p_i$在A数组中的左侧那么$q_i$就在A数组的右测

反之若$p_i$在A数组的右测那么$q_i$就在A数组的左侧

由于q是非严格递减 p是非严格递增

所以在A数组中pi的取值往右侧移动时 qi的取值则在往左侧移动

现在假如一个中间点mid=n 它左侧为L区域右侧为R区域,根据这种模糊的感觉

得到假设pi和qi一定会在中点mid的两侧

若这个假设成立那么无论如何选择n个数组成$q$和$p$

他们对应的花费$f(p,q)=∑_{i=1}^n|p_i-q_i|$ 总等于 $SumR-SumL$

即排序后A数组右侧n个数之和-A数组左侧n个数之和

为什么对于任意一对$(p,q)$ 它的花费$f(p,q)=∑_{i=1}^n|p_i-q_i|$ 总等于 $SumR-SumL$

假设pi在L区域内 ,qi在R区域内那么有$p_i-q_i<0$ 变为$L_x-R_y<0$

取绝对值后得到 $|p_i-q_i|=R_y-L_x$

假设pi在R区域内 ,qi在L区域内那么有$p_i-q_i>0$ 变为$R_x-L_y>0$

取绝对值后得到 $|p_i-q_i|=R_x-L_y$

所以对于任意一对(p,q)总有 $f(p,q)=∑_{i=1}^n|p_i-q_i|= SumR-SumL$ 成立

为什么$p_i$和$q_i$ 一定在mid两侧

假若$p_i$和$q_i$ 都在R区域那么$p_{i+1}$~$p_n$ 都在R区域

同时$q_1$~$q_i$ 都在R区域那么R区域共有n+1个数。这与事实不符

假若假若$p_i$和$q_i$ 都在L区域那么$p_{1}$~$p_{i}$ 都在L区域

同时$q_{i}$~$q_{n}$ 都在L区域那么L区域共有n+1个数

于是只要求出可以选出多少对(p,q) 就能直接得到答案

设T为共有多少对(p,q)则 T=C(2n,n) 即从2n个数中选出n个数放入p剩下的自然分组到q

1 2	inv[1]=1; inv[0]=0; ///将0的逆元定为1是因为求组合数时C(n,0)=C(n,n)=1 inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;

对于组合数求逆元可以先$On$ 递推预处理得到。顺便提一下组合数公式

C(n,a)=n!/a!×(n-a)!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=3e5+5;
const int Mod=998244353;
const ll inf=1e18;

/*
*/
ll F[Max];
ll arr[Max];
ll inv[Max];
ll C[Max];
int main(){
    Turnoff;
    int n;cin>>n;
    inv[1]=1;F[1]=1;inv[0]=1;
    for(ll i=2;i<=2*n;i++){
        inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
        F[i]=F[i-1]*i%Mod;
    }
    for(int i=1;i<=n;i++)inv[i]=inv[i]*inv[i-1]%Mod;
    for(int i=0;i<2*n;i++)cin>>arr[i];
    sort(arr,arr+2*n);ll L=0,R=0;
    for(int i=0;i<n;i++)L=(L+arr[i])%Mod;
    for(int i=n;i<2*n;i++)R=(R+arr[i])%Mod;
    ll T=F[2*n]*inv[n]%Mod*inv[n]%Mod;///C(2n,n)
    ll ans=(Mod+R-L)%Mod*T%Mod;
    cout<<ans<<endl;
}

查看评论

codeforces-#680-D

codeforces-#680-D

题意

题解

C(n,a)=n!/a!×(n-a)!