首页 > 其他分享 >[题解]AT_abc151_e [ABC151E] Max-Min Sums

[题解]AT_abc151_e [ABC151E] Max-Min Sums

时间:2024-06-22 10:54:48浏览次数:23  
标签:排序 abc151 Min int 题解 fac mod define

思路

考虑将 \(\max\) 和 \(\min\) 的贡献分开计算。

显然我们对这个序列进行一次排序不会影响最终的答案,因此我们可以先排序一下。

然后有一个很经典的 trick,就是你枚举每一个数 \(x\),将 \(x\) 令为最大值(最小值)。因为我们先前排序过一次,因此我们可以轻易的计算出比 \(x\) 小(大)的数的数量,然后我们需要在这些数里面选出剩下的 \(k - 1\) 个数,直接组合数算一下,得出方案数 \(num\)。那么 \(x\) 的贡献就是 \(num \times x\)。

Code

#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) (((a) % mod + (b) % mod) % mod)
#define Sub(a,b) (((a) % mod - (b) % mod + mod) % mod)
#define Mul(a,b) (((a) % mod) * ((b) % mod) % mod)

using namespace std;

const int N = 1e5 + 10,mod = 1e9 + 7;
int n,k,a,b;
int arr[N],fac[N],inv[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline int qmi(int a,int b){
    int res = 1;
    while (b){
        if (b & 1) res = Mul(res,a);
        a = Mul(a,a);
        b >>= 1;
    }
    return res;
}

inline void init(){
    fac[0] = 1;
    for (re int i = 1;i <= n;i++) fac[i] = Mul(fac[i - 1],i);
    inv[n] = qmi(fac[n],mod - 2);
    for (re int i = n - 1;~i;i--) inv[i] = Mul(inv[i + 1],i + 1);
}

inline int C(int n,int m){
    if (n < m) return 0;
    return Mul(Mul(fac[n],inv[m]),inv[n - m]);
}

signed main(){
    n = read();
    k = read();
    init();
    for (re int i = 1;i <= n;i++) arr[i] = read();
    sort(arr + 1,arr + n + 1);
    for (re int i = 1;i <= n;i++){
        a = Add(a,Mul(C(n - i,k - 1),arr[i]));
        b = Add(b,Mul(C(i - 1,k - 1),arr[i]));
    }
    printf("%lld",Sub(b,a));
    return 0;
}

标签:排序,abc151,Min,int,题解,fac,mod,define
From: https://www.cnblogs.com/WaterSun/p/18261941

相关文章

  • [题解]AT_abc236_e [ABC236E] Average and Median
    思路直接将输出的答案分为两个分考虑。(1)考虑二分+DP。设当前二分出的平均数为\(x\),如果合法,那么有(其中\(p\)为选出数下标的集合):\[\frac{a_{p_1}+a_{p_2}+\dots+a_{p_k}}{k}\geqx\]即:\[\frac{(a_{p_1}-x)+(a_{p_2}-x)+\dots+(a_{p_......
  • <十三>vue-admin-template 添加标签页
    给template添加 tagsview1、从下载vue-element-admin中下载相关文件到相关目录拷贝文件夹vue-element-admin-master\src\layout\components\TagsView到相同目录下拷贝js文件vue-element-admin-master\src\store\modules\tagsView.js到相同目录下2、修改vue-admin-template......
  • 2020C++等级考试二级真题题解
     202012数组指定部分逆序重放c++ #include<iostream>usingnamespacestd;intmain(){  inta[110];  intn,k;  cin>>n>>k;  for(inti=0;i<n;i++){    cin>>a[i];  }  for(inti=0;i<k/2;i++){......
  • QOJ #8473. Matrices and Determinants
    唉,不会线性代数了,做了三个小时。为了求行列式,显然要先把\(A\)消成上三角矩阵,记作\(A'\)。我们显然可以在操作\(A\)的时候求出将\(A\)消成\(A'\)的操作矩阵\(M\),则我们可以构造\(A'=B'C'\),再将\(B'\)乘上\(M^{-1}\)就可以得到原来的\(B\)。判掉\(A\)的行列式不......
  • 题解:P10641 BZOJ3252 攻略
    我让cz搬这道题,cz给搬了,于是来写个题解(考虑一个朴素的贪心:每次选择一个到根路径价值和最大的叶子,将价值和累加进答案,并把这条链价值清零。这个贪心的正确性显然(可以交换法证明),很容易用数据结构维护做到\(O(n\logn)\)。但是这样太不优美了,而且数据结构比较难写,于是考虑一个......
  • 【MindSpore学习打卡】初学教程-04数据集 Dataset-使用MindSpore实现高效数据加载与预
    在深度学习的世界里,数据是模型训练的根基。高质量的数据输入不仅能提升模型的性能,还能加速训练过程。MindSpore提供了一个强大的数据引擎,通过数据集(Dataset)和数据变换(Transforms)实现高效的数据预处理。本文将详细介绍如何使用MindSpore加载和处理数据集,并通过具体的示例......
  • 【MindSpore学习打卡】初学教程-03张量Tensor-理解MindSpore中的张量(Tensor)操作
    03张量Tensor-理解MindSpore中的张量(Tensor)操作在深度学习领域,张量(Tensor)是最基本的数据结构之一。它不仅可以表示标量、向量和矩阵,还可以表示更高维度的数据。张量在神经网络的构建和训练中扮演着至关重要的角色。在MindSpore中,张量是网络运算的基本单位。本篇博客将详......
  • ABC 330 F Minimize Bounding Square
    题意给定xoy平面上的N个点,可以进行K次操作,每一次操作可以让这N个点中的一个点横向或纵向移动一个单位。最后用一个所有边都平行于x轴或y轴的正方形将这N个点包围,请最小化这个正方形的边长。思路最小化最大横向或纵向长度,显然二分答案。二分最后正方形的长度,现在问题转化为如何c......
  • P8500 [NOI2022] 冒泡排序 题解
    考虑特殊性质B。限制相当于钦定一些位置的值,其他位置无限制。可以发现性质:无限制的位置上填的值是单调不减的。证明:设得到的最优序列为\(A\),对于无限制的位置\(i,j\),若\(A_i>A_j\),交换\(i,j\)后逆序对个数必然减小。根据改性质,只需考虑每个位置对已经确定位置的位置的贡......
  • navicat 数据传输总是 出现select * Process terminated
    navicat数据传输总是出现select*Processterminated报错解释:Navicat在进行数据传输时,如果遇到“select*Processterminated”错误,通常意味着Navicat在执行查询操作时被中断或终止了。这可能是因为查询执行时间过长,超出了设置的限制,或者是因为数据库连接不稳定、......