【NOIP 2024】遗失的赋值

[Problem Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription]

在这里插入图片描述

[Analysis] \color{blue}{\texttt{[Analysis]}} [Analysis]

疑似某退役 OIer 重新回归打 NOIP。

个人觉得比 T1 要简单,主要是贪心题是真的不敢写。

首先,我们可以发现:如果位置 i i i ( i + 1 ) (i+1) (i+1) 都没有一元限制的话,那么可能的方案数就有 v 2 v^2 v2 种。

主要就来考虑 i i i 或者 ( i + 1 ) (i+1) (i+1) 有限制的情况。发现,好像还是 v 2 v^{2} v2 种(在不都有限制的情况下)。所以,这样思考肯定是没有作用的。

那就考虑相邻的两个有限制的点之间的方案数。假设这相邻的两点为 x x x y y y(不妨设 y > x y>x y>x)。如果没有限制的话,那么这两点间的方案数应该是 v 2 ( y − x ) v^{2(y-x)} v2(yx)。考虑不合法的二元限制的数量。

怎样的限制是不合法的呢?很显然是 x x x 限制了 ( x + 1 ) (x+1) (x+1) 取某个特定的值, ( x + 1 ) (x+1) (x+1) 又限制 ( x + 2 ) (x+2) (x+2),以此类推,直到 ( y − 1 ) (y-1) (y1) 限制 y y y 的取值,且 y y y 被限制的取值不为它被一元限制所规定的取值。

形式化地说,就是:

a λ = d x , b λ ∈ [ 1 , v ] a_{\lambda}=d_{x},b_{\lambda} \in [1,v] aλ=dx,bλ[1,v]

a λ + 1 = b λ , b λ + 1 ∈ [ 1 , v ] a_{\lambda+1}=b_{\lambda},b_{\lambda+1} \in [1,v] aλ+1=bλ,bλ+1[1,v]

a λ + 2 = b λ + 1 , b λ + 2 ∈ [ 1 , v ] a_{\lambda+2}=b_{\lambda+1},b_{\lambda+2} \in [1,v] aλ+2=bλ+1,bλ+2[1,v]

⋯ \cdots

a μ = b μ − 1 , b μ ∈ [ 1 , v ] , b μ ≠ d y a_{\mu}=b_{\mu-1},b_{\mu} \in [1,v],b_{\mu} \not = d_{y} aμ=bμ1,bμ[1,v],bμ=dy

用手指头即可知道不合法的方案数为 ( v − 1 ) × v y − x − 1 (v-1) \times v^{y-x-1} (v1)×vyx1

于是在区间 [ x , y ] [x,y] [x,y] 中合法的方案数为 v 2 ( y − x ) − ( v − 1 ) × v y − x − 1 v^{2(y-x)}-(v-1) \times v^{y-x-1} v2(yx)(v1)×vyx1

分段累计即可。

注意特判同一条一元限制多次出现或相互排斥的一元限制出现的情况。

[Code] \color{blue}{\text{[Code]}} [Code]

int n,k,m,v,ans,T;struct Limits{int pos,val;bool operator < (const Limits t) const{return pos<t.pos;}
}lim_init[N],lim[N];int ksm(int a,int p){int res=1;while (p){if (p&1) res=1ll*res*a%mod;a=1ll*a*a%mod;p>>=1;}return res;
}void read_data(){n=read();k=read();v=read();for(int i=1;i<=k;i++){lim_init[i].pos=read();lim_init[i].val=read();}sort(lim_init+1,lim_init+k+1); 
}//Read the data and preliminarily process the databool check_data(){lim[m=1]=lim_init[1];for(int i=2;i<=k;i++)if (lim_init[i].pos==lim_init[i-1].pos){if (lim_init[i].val!=lim_init[i-1].val) return false;}else lim[++m]=lim_init[i];return true;
}//check if any possible solution is existint HPXXZYY(){read_data();if (!check_data())return printf("0\n");ans=ksm(v,(lim[1].pos-1)<<1);for(int i=2;i<=m;i++){int tmp=(ksm(v,(lim[i].pos-lim[i-1].pos)<<1)-1ll*(v-1)*ksm(v,lim[i].pos-lim[i-1].pos-1)%mod+mod)%mod;ans=1ll*ans*tmp%mod;}ans=1ll*ans*ksm(v,(n-lim[m].pos)<<1)%mod;return printf("%d\n",ans);
}int main(){T=read();while (T--) HPXXZYY();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/33798.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

day05【入门】MySQL学习(2)

今日继续学习MySql数据库部分&#xff0c;这块用的比较多的是带有各种条件的select。 目录 1、students表准备&#xff08;查询&#xff09; 2、字段的别名 3、表的别名 4、distinct 过滤重复记录 5、where子句 6、select 查询的基本规律 7、比较运算法 8、逻辑运算符 …

江南大学《2024年807自动控制原理真题》 (完整版)

本文内容&#xff0c;全部选自自动化考研联盟的&#xff1a;《江南大学807自控考研资料》的真题篇。后续会持续更新更多学校&#xff0c;更多年份的真题&#xff0c;记得关注哦~ 目录 2024年真题 Part1&#xff1a;2024年完整版真题 2024年真题

PDF文件页面转换成图片怎么弄-免费PDF编辑工具分享

>>更多PDF文件处理应用技巧请前往 96缔盟PDF处理器 主页 查阅&#xff01; —————————————————————————————————————— 序言 我之前的文章也有介绍过如何使用96缔盟PDF处理器对PDF文件转换成图片&#xff0c;但是当时是使用DMPDFU…

菲涅尔透镜加工:倚光科技的光学创新之路

在光学元件的广袤星空中&#xff0c;菲涅尔透镜以其独特的设计和卓越的性能闪耀着独特光芒。菲涅尔透镜通过将透镜表面由一系列同心棱纹组成&#xff0c;大幅减少了材料的使用量&#xff0c;却依然能够有效地汇聚或发散光线&#xff0c;在众多领域展现出无可比拟的优势&#xf…

电机瞬态分析基础(14):电机的电磁转矩

1. 电机的电磁转矩和转子运动方程 在电机驱动系统中&#xff0c;电动机向其驱动的负载提供驱动转矩&#xff0c;对负载运动的控制是通过对电动机电磁转矩的控制而实现的&#xff0c;如图1所示。 图1. 电动机驱动系统 由图1&#xff0c;根据动力学原理&#xff0c;可列写出机械运…

节点操作+

DOM节点查找节点增加节点删除节点 查找父节点&#xff1a; 想要关闭三个类名都为box1的其中一个&#xff0c;点哪个关哪个 查找子节点&#xff1a; 增加节点&#xff1a; 放到后面 放到前面&#xff08;两个参数&#xff09; 删除节点&#xff1a;

VUE拖拽对象到另一个区域

最近有个需求是需要在web端定制手机的界面UI&#xff08;具体实现比较复杂&#xff0c;此处不做阐述&#xff0c;此文章只说明拖拽效果实现&#xff09;&#xff0c;为了方便用户操作&#xff0c;就想实现这种效果&#xff1a;从右侧的图标列表中拖拽图标到左侧模拟的手机界面上…

优化 LabVIEW 系统内存使用

在 LabVIEW 中&#xff0c;内存使用管理是确保高效系统性能的关键因素&#xff0c;尤其是在进行复杂的数据采集、信号处理和控制任务时。LabVIEW 程序的内存消耗可能会随着项目的规模和复杂度增加&#xff0c;导致性能下降&#xff0c;甚至出现内存溢出或程序崩溃。通过合理优化…

一个实用的端到端的深度学习库存模型

G1 文章信息 文章题为“A Practical End-to-End Inventory Management Model withDeep Learning”&#xff0c;该文于2022年发表至“MANAGEMENT SCIENCE”。文章的核心是提出了端到端的框架用于多周期库存补货问题。 2 摘要 文章研究了一个数据驱动的多周期库存补货问题&am…

STL-需求分析

本小节主要是对要实现的各个功能梳理&#xff0c;理解各个设计之间的关联。&#xff08;未完结&#xff09; 1 list数据结构 可以毫不夸张的说&#xff0c;我们整个项目都是围绕list展开的。因此&#xff0c;我们首先得清楚要使用哪种list。 有请灵魂画手登场&#xff1a; …

STM32进阶 定时器3 通用定时器 案例1:LED呼吸灯——PWM脉冲

功能 它有基本定时器所有功能&#xff0c;还增加以下功能 TIM2、TIM3、TIM4、TIM5 多种时钟源&#xff1a; 外部时钟源模式1&#xff1a; 每个定时器有四个输入通道 只有通道1和通道2的信号可以作为时钟信号源 通道1 和通道2 的信号经过输入滤液和边缘检测器 外部时钟源…

Chrome控制台 网站性能优化指标一览

打开chrome-》f12/右键查看元素-》NetWrok/网络 ctrlF5 刷新网页&#xff0c;可以看到从输入url到页面资源请求并加载网页&#xff0c;用于查看资源加载&#xff0c;接口请求&#xff0c;评估网页、网站性能等&#xff0c;如下图&#xff1a; request、stransferred、resour…

buu ciscn_2019_ne_5

下载附件然后checksec一下如图 32位的程序&#xff0c;nx保护开的&#xff0c;存在栈溢出&#xff0c;拖进ida32中看看 梳理思路&#xff1a; 简单分析并写个注释&#xff0c;这边梳理一下大致流程&#xff0c;先是输入一字符串&#xff0c;然后比对&#xff0c;然后再选择相…

如何降低DApp开发中的Gas费消耗?

Gas费是链上运行DApp时的一项关键成本&#xff0c;直接影响用户体验和应用的吸引力。过高的Gas费可能导致用户流失&#xff0c;尤其在交易密集型应用中。因此&#xff0c;优化Gas费已成为DApp开发者的重要任务。那么&#xff0c;怎样才能有效降低Gas费消耗呢&#xff1f; 1. 优…

CC工具箱使用指南:【湖北省村规结构调整表(D)】

一、简介 群友定制工具。 工具根据输入的现状用地和规划用地图层&#xff0c;生成村域和村庄建设边界内的结构调整表。 二、工具参数介绍 点击【定制2】组里的【湖北省村规结构调整表(D)】工具&#xff1a; 即可打开下面的工具框界面&#xff1a; 1、现状用地图层 2、现状…

逗号分隔、多级位置及局部更新的Sql实现

一、逗号分隔的字符串多值查询 1&#xff0c;背景 假设有一个表location_type_relation&#xff0c;其中有1个字段location_ids&#xff0c;用逗号分隔了多个标签&#xff0c;还有1个字段type_ids&#xff0c;也是用逗号分隔了多个标签 2&#xff0c;需求 现在要判断locat…

flink-connector-mysql-cdc:01 mysql-cdc础配置代码演示

flink-connector-mysql-cdc&#xff1a; 01 mysql-cdc基础配置代码演示02 mysql-cdc高级扩展03 mysql-cdc常见问题汇总04 mysql-cdc-kafka生产级代码分享05 flink-kafka-doris生产级代码分享06 flink-kafka-hudi生产级代码分享 flink-cdc版本&#xff1a;3.2.0 flink版本&…

工业-实时数据采集

1.编写新的 Flume 配置文件&#xff0c;将数据备份到 HDFS 目录 /user/test/flumebackup 下&#xff0c;要求所有主题 的数据使用同一个 Flume配置文件完成。 1. 配置概览 Flume 的主要任务是从多个来源&#xff08;如日志文件&#xff09;读取数据&#xff0c;经过处理后通过…

mmdet 加载预训练模型多卡训练过程中,存在显卡占用显存不均匀

1. 问题描述 基于mmdet https://github.com/open-mmlab/mmdetection代码仓库&#xff0c;修改了自己的检测代码&#xff0c;加载了预训练模型&#xff0c;进行分布式训练。 在训练过程中&#xff0c;出现了显卡的占用显存不均匀的问题。 如图所示&#xff0c;可以看到显卡2 占…