当前位置: 首页 > news >正文

牛客周赛Round 84

本场比赛难度不大,也是本人第一次AK,最后一题用组合数学+推公式,本篇博客主要讲解最后一题的思路

G-小红的陡峭值(五)(hard)_牛客周赛 Round 84

思路:本题要我们求p/q mod M ,即p*(q的逆),q为排列数,我们可以很容易得到,即 n!,但分子为所有排列的陡峭值之和,暴力做法肯定是不行的,于是我们可以通过绝对值的性质:若a2>a1,则|a1-a2|=|a2-a1|=a2-a1,先将数组a进行升序排序,我们可以计算a[i-1]a[i]这对相邻元素会出现在多少种不同的排列中,这里我们可以使用高中学的排列组合来计算,从n个元素中拿出去2个元素,还剩下n-2个元素,那么这n-2个元素就有(n-2)!种摆放方式,再将a[i-1]a[i]插入n-1个空中的任意一个,就可以得到a[i-1]a[i]在(n-2)!*(n-1)=(n-1)!个排列中做出了贡献,而a[i]a[i-1]的贡献与a[i-1]a[i]一样,那么我们要计算出(a[i]-a[i-1])+(a[i]-a[i-2])+(a[i]-a[i-3])+...+(a[i]-a[1])的和,那么这个式子化简一下就是(i-1)*a[i]-pre[i-1],最终我们得到的结果p/q= \frac{2*(\sum_{i=1}^{i=n}Si) *(n-1)!}{n!}=\frac{2*\sum_{i=1}^{i=n}Si}{n}

Code:

int n;int qmi(int a,int b)
{int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;
}
void solve()
{cin >> n;vector<int> v(n+1);for(int i=1;i<=n;i++) cin>>v[i];sort(v.begin()+1,v.end());vector<int> pre(n+1,0);for(int i=1;i<=n;i++) {pre[i]=(pre[i-1]+v[i]%mod)%mod;}int S=0;for(int i=1;i<=n;i++){int b=((v[i]%mod)*(i-1+mod)%mod)%mod;b=(b-pre[i-1]+mod)%mod;S=(S+b)%mod;}int num=(2*S)%mod;int inv=qmi(n,mod-2);int ans=num*inv%mod;cout<<ans<<endl;
}

相关文章:

牛客周赛Round 84

本场比赛难度不大&#xff0c;也是本人第一次AK&#xff0c;最后一题用组合数学推公式&#xff0c;本篇博客主要讲解最后一题的思路 G-小红的陡峭值&#xff08;五&#xff09;&#xff08;hard&#xff09;_牛客周赛 Round 84 思路&#xff1a;本题要我们求p/q mod M ,即p*&am…...

TDengine 配置 ODBC 数据源

简介 TDengine ODBC 是为 TDengine 实现的 ODBC 驱动程序&#xff0c;支持 Windows 系统的应用&#xff08;如 PowerBI 等&#xff09;以及用户自定义开发的应用程序&#xff0c;通过 ODBC 标准接口访问本地、远程和云服务的 TDengine 数据库。 TDengine ODBC 提供基于 WebSo…...

numpy常用函数详解

在深度神经网络代码中经常用到numpy库的一些函数&#xff0c;很多看过之后很容易忘记&#xff0c;本文对经常使用的函数进行归纳总结。 np.arange arange是numpy一个常用的函数&#xff0c;该函数主要用于创建等差数列。它的使用方法如下所示&#xff1a; numpy.arange([star…...

deepseek 3FS编译

3FS在ubuntu22.04下的编译&#xff08;记录下编译过程&#xff0c;方便后续使用&#xff09; 环境信息 OS ubuntu 22.04内核版本 6.8.0-52-genericlibfuse 3.16.1rust 1.75.0FoundationDB 7.1.66meson 1.0.0ninja 1.10.1 libfuse编译 以下建议均在root下执行 pip3 install…...

【CXX】6.2 str — rust::Str

Rust::Str 公共 API // rust/cxx.hclass Str final { public:Str() noexcept;Str(const Str &) noexcept;Str(const String &) noexcept;// 如果输入不是 UTF-8&#xff0c;抛出 std::invalid_argument 异常。Str(const std::string &);Str(const char *);Str(con…...

制作三维软件学习路线

制作三维软件是一项复杂而富有挑战性的任务&#xff0c;涉及多个领域的知识。下面是一个建议的学习路线&#xff0c;涵盖从基础到高级的知识和技能。你可以根据自己的背景和兴趣进行调整。 ### 1. 编程基础 - **学习编程语言**&#xff1a;C或Python是常用的语言&#xff0c;了…...

【RabbitMQ】事务

事务的简单配置及使用 配置事务管理器声明队列生产者代码测试 RabbitMQ是基于AMQP协议实现的&#xff0c;该协议实现了事务机制&#xff0c;因此RabbitMQ也支持事务机制. SpringAMQP也提供了对事务相关的操作.RabbitMQ事务允许开发者确保消息的发送和接收是原子性的&#xff0c…...

常见的交换机端口类型

在计算机网络中&#xff0c;Access端口 和 Trunk端口 是两种常见的交换机端口类型&#xff0c;主要用于VLAN&#xff08;虚拟局域网&#xff09;的配置。它们的主要区别在于如何处理VLAN标签和数据帧。 1. Access端口 Access端口通常用于连接终端设备&#xff08;如PC、打印机…...

Linux Shell 脚本编程极简入门指南

一、学习前提准备 ✅ 环境要求&#xff1a; Linux系统&#xff08;Ubuntu/CentOS等&#xff09;或 WSL (Windows用户) 任意文本编辑器&#xff08;推荐VSCode/Vim&#xff09; 基础命令行操作能力 &#x1f50d; 验证环境&#xff1a; # 查看系统默认Shell echo $SHELL #…...

【医院管理会计专题】7.解锁本量利分析:医院医疗服务决策的智慧密码

医院成本核算、绩效管理、运营统计、内部控制、管理会计专题索引 一、引言 在当今医疗行业竞争日益激烈的背景下,医院管理面临着诸多挑战,如何实现高效运营、提升服务质量并控制成本成为关键问题。管理会计作为一种重要的管理工具,在医院管理中发挥着越来越重要的作用。本…...

Kotlin和Java区别

哈哈哈&#xff0c;前段时间&#xff0c;面试的时候&#xff0c;突然问到我Kotlin和Java的区别&#xff0c;一下子把我问懵逼了&#xff0c;确实没遇到问这个的&#xff0c;想了下&#xff0c;说了下Kotlin的编译时空检查机制&#xff0c;代码更简洁&#xff0c;很多封装好的AP…...

Taro 面试题

基础概念 1. Taro 是什么&#xff1f;它的核心特点有哪些&#xff1f; Taro 是京东开源的 多端统一开发框架&#xff0c;基于 React 语法&#xff0c;可编译到 微信小程序、H5、React Native 等多个端。 核心特点&#xff1a; 多端适配&#xff1a;一套代码运行多个端支持 …...

Java部署在window启动报unable tocreate tempdir

在Windows系统中&#xff0c;Java应用在运行时会试图在默认的临时目录中创建文件。该临时目录通常由系统环境变量TEMP或TMP指定。如果这些变量设置不正确、指向一个无效的路径&#xff0c;或者操作系统的权限不足&#xff0c;就会导致“Unable to create tempdir”错误。 解决…...

基于deepseek和开放题库,构建专业大模型微调在线答题系统

为什么要进行大模型微调 大模型微调是将预训练模型适配到特定任务或领域的关键技术&#xff0c;正常情况下大模型通过海量通用数据训练获得广泛知识&#xff0c;但其参数和表征空间面向通用场景&#xff0c;难以直接适配垂直领域或复杂任务。例如在通用医疗问答模型在具体病症诊…...

ios 小组件和数据共享

创建主工程就不必讲了 1 创建小组件 创建子工程 [new Target ] 选择 [ Widger Extension] 小组件入口是WidgetBundle文件&#xff0c;可以进行多个小组件的调试 TestWidget2文件是主要操作&#xff0c;小组件使用swiftUI布局&#xff0c;使用 AppIntent进行事件处理&#xff…...

LVTTL(Low Voltage Transistor-Transistor Logic)电平详解

一、LVTTL电平的定义与核心特性 LVTTL&#xff08;低压晶体管-晶体管逻辑&#xff09;是传统TTL&#xff08;5V&#xff09;的低电压版本&#xff0c;工作电压通常为3.3V&#xff0c;旨在降低功耗并适配现代低电压集成电路&#xff0c;同时保持与TTL的逻辑兼容性。其核心特点如…...

element tree树形结构默认展开全部

背景&#xff1a; el-tree树形结构&#xff0c;默认展开全部&#xff0c;使用属性default-expand-all【是否默认展开所有节点】&#xff1b;默认展开一级&#xff0c;设置default-expanded-keys【默认展开的节点的 key 的数组】属性值为数组。 因为我这里的数据第一级是四川【省…...

统计登录系统10秒内连续登录失败超过3次的用户

为防止暴力破解用户账号的行为&#xff0c;在输入账号和密码时一般都会限制用户尝试密码输出错误的次数&#xff0c;如果用户多次输错密码后&#xff0c;将在一段时间内锁定账号&#xff0c;常见的有银行类APP、个税App等应用&#xff0c;如下是用户账号密码输入错误的提示图&a…...

音视频软件工程师面试题

一、基础知识 编解码相关 H.264 和 H.265(HEVC)的主要区别是什么?视频编解码的基本流程是什么?关键技术有哪些?音频编解码(如 AAC、MP3、Opus)的区别和应用场景?什么是 B 帧、P 帧、I 帧?它们的作用是什么? 流媒体协议RTMP、HTTP-FLV、HLS、WebRTC 的区别和应用场景…...

架构师面试(十四):注册中心设计

问题 大家或多或少都接触过【注册中心】&#xff0c;对注册中心的基本功能&#xff0c;如&#xff1a;服务注册、服务发现、健康检查和变更通知 &#xff0c;肯定是耳熟能详的&#xff1b;那么大家对注册中心的架构设计是否了解呢&#xff1f; 如果让你负责设计一个分布式的注…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...