当前位置: 首页 > 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; 如果让你负责设计一个分布式的注…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

如何做好一份技术文档?从规划到实践的完整指南

如何做好一份技术文档&#xff1f;从规划到实践的完整指南 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...

接口 RESTful 中的超媒体:REST 架构的灵魂驱动

在 RESTful 架构中&#xff0c;** 超媒体&#xff08;Hypermedia&#xff09;** 是一个核心概念&#xff0c;它体现了 REST 的 “表述性状态转移&#xff08;Representational State Transfer&#xff09;” 的本质&#xff0c;也是区分 “真 RESTful API” 与 “伪 RESTful AP…...