牛客周赛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= =
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
本场比赛难度不大,也是本人第一次AK,最后一题用组合数学推公式,本篇博客主要讲解最后一题的思路 G-小红的陡峭值(五)(hard)_牛客周赛 Round 84 思路:本题要我们求p/q mod M ,即p*&am…...
TDengine 配置 ODBC 数据源
简介 TDengine ODBC 是为 TDengine 实现的 ODBC 驱动程序,支持 Windows 系统的应用(如 PowerBI 等)以及用户自定义开发的应用程序,通过 ODBC 标准接口访问本地、远程和云服务的 TDengine 数据库。 TDengine ODBC 提供基于 WebSo…...
numpy常用函数详解
在深度神经网络代码中经常用到numpy库的一些函数,很多看过之后很容易忘记,本文对经常使用的函数进行归纳总结。 np.arange arange是numpy一个常用的函数,该函数主要用于创建等差数列。它的使用方法如下所示: numpy.arange([star…...
deepseek 3FS编译
3FS在ubuntu22.04下的编译(记录下编译过程,方便后续使用) 环境信息 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,抛出 std::invalid_argument 异常。Str(const std::string &);Str(const char *);Str(con…...
制作三维软件学习路线
制作三维软件是一项复杂而富有挑战性的任务,涉及多个领域的知识。下面是一个建议的学习路线,涵盖从基础到高级的知识和技能。你可以根据自己的背景和兴趣进行调整。 ### 1. 编程基础 - **学习编程语言**:C或Python是常用的语言,了…...
【RabbitMQ】事务
事务的简单配置及使用 配置事务管理器声明队列生产者代码测试 RabbitMQ是基于AMQP协议实现的,该协议实现了事务机制,因此RabbitMQ也支持事务机制. SpringAMQP也提供了对事务相关的操作.RabbitMQ事务允许开发者确保消息的发送和接收是原子性的,…...
常见的交换机端口类型
在计算机网络中,Access端口 和 Trunk端口 是两种常见的交换机端口类型,主要用于VLAN(虚拟局域网)的配置。它们的主要区别在于如何处理VLAN标签和数据帧。 1. Access端口 Access端口通常用于连接终端设备(如PC、打印机…...
Linux Shell 脚本编程极简入门指南
一、学习前提准备 ✅ 环境要求: Linux系统(Ubuntu/CentOS等)或 WSL (Windows用户) 任意文本编辑器(推荐VSCode/Vim) 基础命令行操作能力 🔍 验证环境: # 查看系统默认Shell echo $SHELL #…...
【医院管理会计专题】7.解锁本量利分析:医院医疗服务决策的智慧密码
医院成本核算、绩效管理、运营统计、内部控制、管理会计专题索引 一、引言 在当今医疗行业竞争日益激烈的背景下,医院管理面临着诸多挑战,如何实现高效运营、提升服务质量并控制成本成为关键问题。管理会计作为一种重要的管理工具,在医院管理中发挥着越来越重要的作用。本…...
Kotlin和Java区别
哈哈哈,前段时间,面试的时候,突然问到我Kotlin和Java的区别,一下子把我问懵逼了,确实没遇到问这个的,想了下,说了下Kotlin的编译时空检查机制,代码更简洁,很多封装好的AP…...
Taro 面试题
基础概念 1. Taro 是什么?它的核心特点有哪些? Taro 是京东开源的 多端统一开发框架,基于 React 语法,可编译到 微信小程序、H5、React Native 等多个端。 核心特点: 多端适配:一套代码运行多个端支持 …...
Java部署在window启动报unable tocreate tempdir
在Windows系统中,Java应用在运行时会试图在默认的临时目录中创建文件。该临时目录通常由系统环境变量TEMP或TMP指定。如果这些变量设置不正确、指向一个无效的路径,或者操作系统的权限不足,就会导致“Unable to create tempdir”错误。 解决…...
基于deepseek和开放题库,构建专业大模型微调在线答题系统
为什么要进行大模型微调 大模型微调是将预训练模型适配到特定任务或领域的关键技术,正常情况下大模型通过海量通用数据训练获得广泛知识,但其参数和表征空间面向通用场景,难以直接适配垂直领域或复杂任务。例如在通用医疗问答模型在具体病症诊…...
ios 小组件和数据共享
创建主工程就不必讲了 1 创建小组件 创建子工程 [new Target ] 选择 [ Widger Extension] 小组件入口是WidgetBundle文件,可以进行多个小组件的调试 TestWidget2文件是主要操作,小组件使用swiftUI布局,使用 AppIntent进行事件处理ÿ…...
LVTTL(Low Voltage Transistor-Transistor Logic)电平详解
一、LVTTL电平的定义与核心特性 LVTTL(低压晶体管-晶体管逻辑)是传统TTL(5V)的低电压版本,工作电压通常为3.3V,旨在降低功耗并适配现代低电压集成电路,同时保持与TTL的逻辑兼容性。其核心特点如…...
element tree树形结构默认展开全部
背景: el-tree树形结构,默认展开全部,使用属性default-expand-all【是否默认展开所有节点】;默认展开一级,设置default-expanded-keys【默认展开的节点的 key 的数组】属性值为数组。 因为我这里的数据第一级是四川【省…...
统计登录系统10秒内连续登录失败超过3次的用户
为防止暴力破解用户账号的行为,在输入账号和密码时一般都会限制用户尝试密码输出错误的次数,如果用户多次输错密码后,将在一段时间内锁定账号,常见的有银行类APP、个税App等应用,如下是用户账号密码输入错误的提示图&a…...
音视频软件工程师面试题
一、基础知识 编解码相关 H.264 和 H.265(HEVC)的主要区别是什么?视频编解码的基本流程是什么?关键技术有哪些?音频编解码(如 AAC、MP3、Opus)的区别和应用场景?什么是 B 帧、P 帧、I 帧?它们的作用是什么? 流媒体协议RTMP、HTTP-FLV、HLS、WebRTC 的区别和应用场景…...
架构师面试(十四):注册中心设计
问题 大家或多或少都接触过【注册中心】,对注册中心的基本功能,如:服务注册、服务发现、健康检查和变更通知 ,肯定是耳熟能详的;那么大家对注册中心的架构设计是否了解呢? 如果让你负责设计一个分布式的注…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
