CF Round#680 D.Divide and Sum

Divide and Sum

思维
题意：给出一个长度2n的数列，将其划分为两个数列p、q（只要下标不同即视为不同划分），其中p为降序序列、q为增序序列。定义f(p,q)=sum{|p[i]-q[i]|1<=i<=n}。问所有划分的f值总和。

思路：
首先对2n个数排序，先逐个观察对于其中的a[i] (i<=n),
将其放在数列q(增序)中第t个位置q[t]，
可知q中a[i]右侧的数共（n-t）个都大于等于a[i],
由于共有2n-i个数大于a[i],而2*n-i-(n-t)=n-i+t>=t，
因此p(降序)中至少有t个数且前t个数大于等于a[i]，且p中的第t个元素>=a[i]，
故无论a[i] 放在任一位置其都起负贡献（减数）作用；同理a[i] (i>n)都起正贡献（被减数）作用

因为一共有C(2n,n)种情况，最终总答案 [sum{a[i]|i>n}-sum{a[i]|i<=n}]*C(2n, n)

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int Mod=998244353;
const int inf=0x7f;
const int INF=0x3f3f3f3f;
ll a[maxn];
ll quickpower(ll a, ll k){
ll ans=1;
while(k){
if(k%2) ans=ans*a%Mod;
a=a*a%Mod;
k/=2;
}
return ans;
}
int main(){
int n; scanf("%d",&n);
for(int i=1;i<=2*n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+2*n+1);
ll res=0;
for(int i=2*n;i>=n+1;i--) res=(res+a[i])%Mod;
for(int i=n;i>=1;i--) res=(res-a[i]+Mod)%Mod;
for(int i=n+1;i<=2*n;i++) res=res*i%Mod;
ll tmp=1;
for(int i=1;i<=n;i++) tmp=tmp*i%Mod;
tmp=quickpower(tmp, Mod-2);
res=res*tmp%Mod;
printf("%lldn",res);
}

最后

以上就是无语钢笔为你收集整理的CF Round#680 D.Divide and Sum的全部内容，希望文章能够帮你解决CF Round#680 D.Divide and Sum所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。