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

P8649 [蓝桥杯 2017 省 B] k 倍区间:同余,前缀和,组合数,区间个数

题目描述

给定一个长度为 NN 的数列,A1,A2,⋯ANA1​,A2​,⋯AN​,如果其中一段连续的子序列 Ai,Ai+1,⋯Aj(i≤j)Ai​,Ai+1​,⋯Aj​(i≤j) 之和是 KK 的倍数,我们就称这个区间 [i,j][i,j] 是 KK 倍区间。

你能求出数列中总共有多少个 KK 倍区间吗?

输入格式

第一行包含两个整数 NN 和 KK(1≤N,K≤105)(1≤N,K≤105)。

以下 NN 行每行包含一个整数 AiAi​(1≤Ai≤105)(1≤Ai​≤105)。

输出格式

输出一个整数,代表 KK 倍区间的数目。

输入输出样例

输入 #1复制

5 2
1  
2  
3  
4  
5  

输出 #1复制

6

说明/提示

时限 2 秒, 256M。蓝桥杯 2017 年第八届

做法

这题我们用前缀和来写,暴力做法是对于每个右端点,枚举每个左端点,符合的区间就加一,当然,这太暴力了。我们求区间个数一般都是先遍历右端点,然后左端点个数 O(1) 就能求出来了,就是直接查询。

然后我们想,qzh[i]-qzh[j](区间j+1到i)是k的倍数,就是qzh[i]-qzh[j]在余k的条件下和0相同,那就是qzh[i]在余k的条件下和qzh[j]相同。那么,我们枚举右端点,只要有和它的余数相同的,就是符合的左端点。但是这样复杂度并没有降下去。

其实正确做法是,我们知道了0到k-1的每个余数的个数,那么我们就从中选两个,有多少种组合,就有多少个区间。这就用到了组合数。

有一个特殊情况,当余数是0时,单个也是符合条件的,所以要再加上余数是0的个数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,k,sum,ans;
map<int,int> mp;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){cin>>a;sum+=a%k;sum%=k;mp[sum]++;}for(int i=0;i<k;i++){if(i==0) ans+=mp[i]*(mp[i]-1)/2+mp[i];else{ans+=mp[i]*(mp[i]-1)/2;}}cout<<ans;}

相关文章:

P8649 [蓝桥杯 2017 省 B] k 倍区间:同余,前缀和,组合数,区间个数

题目描述 给定一个长度为 NN 的数列&#xff0c;A1,A2,⋯ANA1​,A2​,⋯AN​&#xff0c;如果其中一段连续的子序列 Ai,Ai1,⋯Aj(i≤j)Ai​,Ai1​,⋯Aj​(i≤j) 之和是 KK 的倍数&#xff0c;我们就称这个区间 [i,j][i,j] 是 KK 倍区间。 你能求出数列中总共有多少个 KK 倍区…...

产业与学术相互促进,2024年OEG海上能源博览会助力全球能源可持续发展

10月30日至31日&#xff0c;2024年OEG海上能源全产业链博览会在上海跨国采购会展中心成功举办。本次大会系全球海洋工程与高端装备领域的年度国际交流盛会——第十一届全球FPSO&FLNG&FSRU大会&#xff0c;同期举办第七届亚洲海洋风能大会。本次大会暨博览会由上海船舶工…...

【GDB调试】智慧中控项目的调试

一.在执行的智慧中控项目的时候&#xff0c;喊语音模块唤醒(小欣小欣)的时候遇到了&#xff1a;Segmentation fault 段错误 二.遇到段错误&#xff0c;一般是以下情况&#xff1a; “Segmentation fault”&#xff08;段错误&#xff09;是Linux系统中常见的程序异常终止信号。…...

《一本书讲透 Elasticsearch》京东评论采集+存储+可视化全 AI 实现

经常和出版社编辑老师交流读者的反馈。毕竟是小众书籍&#xff0c;豆瓣评分的人并不多。 而京东作为主要读书销售渠道&#xff0c;非常有必要整合一下京东读者评论&#xff0c;看看读者们都说了什么&#xff0c;以便后续的改进&#xff01; 一条条的翻看非常不方便&#xff0c;…...

uniapp中webview全屏不显示导航栏解决方案

uniapp官网文档地址&#xff1a;https://uniapp.dcloud.net.cn/api/window/window.html#getappwebview <template><view class"index"><u-navbar :is-back"true" title"标题"" :title-width"650"></u-navb…...

Dear ImGui 使用VS2022编译为静态库

Dear ImGui 是一个无臃肿的 C++ 图形用户界面库。它输出优化的顶点缓冲区,您可以在支持 3D 管道的应用程序中随时渲染这些缓冲区。它速度快、可移植、与渲染器无关且自成一体(无外部依赖项)。 Dear ImGui 旨在实现快速迭代,并让程序员能够创建内容创建工具和可视化/调试工具…...

5G 现网信令参数学习(3) - RrcSetup(1)

目录 1. rlc-BearerToAddModList 1.1 rlc-Config 1.1.1 ul-AM-RLC 1.1.2 dl-AM-RLC 1.2 mac-LogicalChannelConfig 2. mac-CellGroupConfig 2.1 schedulingRequestConfig 2.2 bsr-Config 2.3 tag-Config 2.4 phr-Config 2.5 skipUplinkTxDynamic 3. physicalCellG…...

PHP实现身份证OCR识别API接口

随着社会的发展&#xff0c;身份认证需求不断增长&#xff0c;这与身份证OCR识别技术的发展密切相关。在当今社会&#xff0c;各个领域都需要进行身份认证。传统的人工手动录入身份证信息费时费力&#xff0c;速度慢且容易出错&#xff0c;体验不佳。而身份证 OCR 识别技术通过…...

关于 Qt+Osg中使用背景图HUD受到后绘制几何图形顶点颜色影响 的解决方法

若该文为原创文章&#xff0c;转载请注明出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/143607816 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV、Op…...

[CKS] K8S AppArmor Set Up

最近准备花一周的时间准备CKS考试&#xff0c;在准备考试中发现有一个题目关于AppArmor Pod操作权限的问题。 ​ 专栏其他文章: [CKS] Create/Read/Mount a Secret in K8S-CSDN博客[CKS] Audit Log Policy-CSDN博客 -[CKS] 利用falco进行容器日志捕捉和安全监控-CSDN博客[CKS] …...

redis笔记-数据结构

zset zset一方面它是一个 set&#xff0c;保证了内部value 的唯一性&#xff0c;另一方面它可以给每个 value 赋予一个 score&#xff0c;代表这个 value 的排序权重。 zset的底层是由字典和跳表实现。 字典主要用来存储value和score的对应关系。跳表这个数据结构主要用来提…...

webpack的常见配置

Webpack 是一个现代 JavaScript 应用的模块打包工具&#xff0c;用于将项目中的多个文件和依赖打包成浏览器可以识别的文件&#xff0c;通常是一个或多个 JavaScript、CSS 或其他静态资源的 bundle&#xff08;将多个模块或文件合并成一个或几个文件的过程&#xff0c;这些合并…...

text-embedding-ada-002;BGE模型;M3E模型是Moka Massive Mixed Embedding;BERT

目录 text-embedding-ada-002 一、模型概述 二、模型功能 三、模型特点 四、模型应用 五、模型优势 BGE模型 一、模型背景与特点 二、模型性能与表现 三、模型迭代与发展 M3E模型是Moka Massive Mixed Embedding 一、基本信息 二、技术特点 三、应用场景 四、性能…...

WebRTC 环境搭建

主题 本文主要描述webrtc开发过程中所需的环境搭建 环境&#xff1a; 运行环境&#xff1a;ubuntu 20.04 Node.js环境搭建 安装编译 Node.js 所需的依赖包: sudo apt-get update sudo apt-get install -y build-essential libssl-dev 下载 Node.js 源码: curl -sL htt…...

FastHTML快速入门:http方法,CSS文件和内联样式,其他静态媒体文件位置

HTTP方法 FastHTML通过函数名与HTTP方法进行匹配。到目前为止&#xff0c;我们定义的URL路由都是针对HTTP GET方法的&#xff0c;这是网页最常见的方法。 表单提交通常作为HTTP POST发送。在处理更动态的网页设计时&#xff0c;也就是所谓的单页应用&#xff08;SPA&#xff0…...

项目管理和研发管理中的痛点及其解决方案

在现代企业中&#xff0c;研发管理和项目管理面临着多重挑战&#xff0c;包括资源配置不当、沟通不畅、目标不明确、进度控制困难等。这些痛点不仅影响项目的顺利推进&#xff0c;还可能导致企业在市场竞争中处于劣势。尤其是在资源配置不当方面&#xff0c;企业往往难以合理分…...

机器学习(基础1)

数据集 sklearn玩具数据集 数据量小&#xff0c;数据在sklearn库的本地&#xff0c;只要安装了sklearn&#xff0c;不用上网就可以获取 sklearn现实世界数据集 数据量大&#xff0c;数据只能通过网络获取&#xff08;为国外数据集&#xff0c;下载需要梯子&#xff09; skle…...

我谈维纳(Wiener)复原滤波器

Rafael Gonzalez的《数字图像处理》中&#xff0c;图像复原这章内容几乎全错。上篇谈了图像去噪&#xff0c;这篇谈图像复原。 图像复原也称为盲解卷积&#xff0c;不处理点扩散函数&#xff08;光学传递函数&#xff09;的都不是图像复原。几何校正不属于图像复原&#xff0c…...

怎么看真假国企啊?怎么识别假冒国企的千层套路?

一、怎么看真假国企啊&#xff1f; 1.使用具有迷惑性的名称&#xff1a;假冒国企往往在名称中使用“中国”、“中”、“国”等字样&#xff0c;或与知名国企名称相似的字号&#xff0c;以增加其可信度。 2.注册资本虚高&#xff1a;为了显示实力&#xff0c;假冒国企可能会在…...

C#中break和continue的区别?

在C#编程语言中&#xff0c;break和continue是两个用于控制循环流程的关键字&#xff0c;但它们的作用和用途有所不同。 break关键字 break关键字用于立即终止它所在的最内层循环或switch语句&#xff0c;并跳出该循环或switch块。程序执行将继续进行循环或switch语句之后的下一…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...