AcWing 1230.K倍区间
AcWing 1230. K倍区间
题目描述
给定一个长度为 NNN 的数列,A1,A2,…ANA_1, A_2, … A_NA1,A2,…AN ,如果其中一段连续的子序列 Ai,Ai+1,…AjA_i, A_{i+1}, … A_jAi,Ai+1,…Aj 之和是 KKK 的倍数,我们就称这个区间 [i,j][i,j][i,j] 是 KKK 倍区间。
你能求出数列中总共有多少个 KKK 倍区间吗?
输入格式
第一行包含两个整数 NNN 和 KKK。
以下 NNN 行每行包含一个整数 AiA_iAi。
输出格式
输出一个整数,代表 KKK 倍区间的数目。
数据范围
1≤N,K≤1000001≤N,K≤1000001≤N,K≤100000,
1≤Ai≤1000001≤A_i≤1000001≤Ai≤100000
输入样例:
5 2
1
2
3
4
5
输出样例:
6
思路
求区间 [l,r][l,r][l,r] 的和是 kkk 的倍数的个数。
求区间和,我们可以通过 前缀和 来求出。
定义 sum[i] 表示第 111 个元素到第 iii 个元素的和,那么 s[r] - s[l-1] 就是区间 [l,r][l,r][l,r] 的和。
若满足条件:区间 [l,r][l,r][l,r] 的和是k的倍数,即 (s[r] - s[l-1]) % k == 0 ,等价于 s[r] % k == s[l-1] % k 。
说人话,这也就意味着:
如果
s[r] mod k和s[l - 1] mod k的余数相等,那么s[r] - s[l - 1]的差值必然是 kkk 的倍数。比如:13 % 7 == 20 % 7,则 (20 - 7) % 7 == 0
那么题目就是要我们求 前缀和%k==0 的组合有多少种。
用 cnt[i] 存储目前为止前缀和相同的个数,iii 表示这个前缀和的值。
每次用 res 来递加 cnt[i] 相同的个数,前面有几个 前缀和的值 和 当前前缀和 相等,那么这个前缀和就能和前面每一个组成一个组合,所以要 res += cnt[s[i]] ,然后再加上现在的前缀和,即 cnt[s[i]]++ 。
初始化 cnt[0] = 1 ,因为当 s[i] == 0 时,这个前缀和本身就是 kkk 的倍数,不需要再跟别的前缀和组合,计算结果时就要加上这一个。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 10;int n, k;
ll s[N];
ll cnt[N];int main()
{cin >> n >> k;ll res = 0;cnt[0] = 1;for (int i = 1; i <= n; i++){cin >> s[i];s[i] = (s[i] + s[i - 1]) % k; //每次前缀和都取模res += cnt[s[i]]; //和前面每一个都组合一下cnt[s[i]]++; //现在又多了一个}cout << res << endl;return 0;
}
相关文章:
AcWing 1230.K倍区间
AcWing 1230. K倍区间 题目描述 给定一个长度为 NNN 的数列,A1,A2,…ANA_1, A_2, … A_NA1,A2,…AN ,如果其中一段连续的子序列 Ai,Ai1,…AjA_i, A_{i1}, … A_jAi,Ai1,…Aj 之和是 KKK 的倍数,我们就称这个区间 [i,j][i,j][i,…...
kubernetes集群部署springcloud项目【AL】【未写完】
kubernetes集群部署springcloud项目【AL】 (先手工做,非自动化) #环境: 192.168.73.138 master 192.168.73.139 node1 192.168.73.140 node2 192.168.73.137 harbor、mysqlgit clone https://github.com/lizhenliang/simple-…...
各种音频接口比较
时间 参考:https://www.bilibili.com/video/BV1SL4y1q7GZ/?spm_id_from333.337.search-card.all.click&vd_source00bd76f9d6dc090461cddd9f0deb2d51, https://blog.csdn.net/weixin_43794311/article/details/128941346 接口名字时间公司支持格式…...
软件测试面试理论(超详细)
【面试理论知识】1、你的测试职业发展是什么? 测试经验越多,测试能力越高。所以我的职业发展是需要时间积累的,一步步向着高级测试工程师奔去。而且我也有初步的职业规划,前3年积累测试经验,按如何做好测试工程师的要点去要求自己…...
c++学习笔记-二进制文件操作(哔站-黑马程序员c++教学视频)
一、基本概念 以二进制的方式对文件进行读写操作 打开方式指定为 ios::binary 优点:可以写入自己定义的数据类型 1、写文件 二进制方式写文件:流对象调用成员write 函数原型:ostream& write(const char * buffer,int len);参数解释…...
内网渗透(二十三)之Windows协议认证和密码抓取-Mimikatz介绍和各种模块使用方法
系列文章第一章节之基础知识篇 内网渗透(一)之基础知识-内网渗透介绍和概述 内网渗透(二)之基础知识-工作组介绍 内网渗透(三)之基础知识-域环境的介绍和优点 内网渗透(四)之基础知识-搭建域环境 内网渗透(五)之基础知识-Active Directory活动目录介绍和使用 内网渗透(六)之基…...
Nginx if的使用教程
if指令该指令用来支持条件判断,并根据条件判断结果选择不同的Nginx配置。语法if (condition){...}默认值—位置server、locationcondition为判定条件,可以支持以下写法:1. 变量名。如果变量名对应的值为空字符串或"0",i…...
备考蓝桥杯【快速排序和归并排序】
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...
Taro使用微信OCR插件无法调用onSuccess回调问题
Taro使用微信插件无法调用onSuccess回调问题小程序后台添加插件在开放社区购买相应的套餐详细步骤1.在app.config.js中添加如下代码2.在页面的page.config.js添加插件3.使用ocr-navigator识别身份证小程序后台添加插件 在开放社区购买相应的套餐 购买地址 详细步骤 1.在app.…...
【Java】代码块的细节你搞懂了吗(基础知识七)
希望像唠嗑一样,one step one futher。 目录 (1)代码块的应用场景 (2)代码块的细节 1.static 代码块只加载一次 2.当调用类的静态成员时,类会加载 3. 使用类的静态成员时,static代码块会被执…...
设计模式C++实现12:抽象工厂模式
参考大话设计模式; 详细内容参见大话设计模式一书第十五章,该书使用C#实现,本实验通过C语言实现。 抽象工厂模式(Abstract Factory),提供一个创建一系列相关或相互依赖对象的接口,而无需指定它们…...
目标检测论文阅读:GraphFPN算法笔记
标题:GraphFPN: Graph Feature Pyramid Network for Object Detection 会议:ICCV2021 论文地址:https://ieeexplore.ieee.org/document/9710561/ Abstract 特征金字塔已经被证明在需要多尺度特征的图像理解任务中是强大的。SOTA的多尺度特征…...
实测2023款哪吒U-II,智驾功能对女司机很友好
最近,我们受邀试驾了2023款哪吒U-II。这是一款A级新能源SUV,是哪吒U的改款车型。哪吒U系列自2020年3月上市到2023年1月,累计销售数量达76688台,也因此被称为15万级智能天花板。2023款哪吒U-II的一大亮点是:针对以往哪吒…...
Python自动化测试【软件测试最全教程(附笔记、学习路线)】,看完即就业
最近看到很多粉丝在后台私信我,叫我做一期Python自动化测试的教程,其实关于这个问题,我也早就在着手准备了,我录制了一整套完整的Python自动化测试的教程,上传到网盘里了,大家有兴趣的可以去文末交流群免费…...
2023/2/13总结
今天主要学习了哈夫曼树。 哈夫曼树 哈夫曼树是二叉树的一种,它是一种WPL最优二叉树。 叶子结点(也称叶节点):指的是自己下面不再连接有节点的节点(即末端),称为叶子节点(又称为终…...
webSock前端
1.什么是webSocket WebSocket是一种在单个TCP连接上进行全双工通信的协议。允许服务端主动向客户端推送数据。 2.如何使用webSocket WebSocket 构造函数WebSocket 对象作为一个构造函数,用于新建 WebSocket 实例。 代码如下: let ws = new WebSocket(网址); 2.websock事件: …...
AcWing 3956. 截断数组(每日一题)
AcWing 3956. 截断数组 题目描述 给定一个长度为 nnn 的数组 a1,a2,…,ana_1, a_2, …, a_na1,a2,…,an 。 现在,要将该数组从中间截断,得到三个非空子数组。 要求,三个子数组内各元素之和都相等。 请问,共有多少种不同…...
Android 一体机研发之修改系统设置————屏幕亮度
Android 一体机研发之修改系统设置————屏幕亮度 Android 一体机研发之修改系统设置————声音 Android 一体机研发之修改系统设置————自动锁屏 前言 最近工作略微有点儿空闲,抽空给大家总结一下:近期一直搞得一体机app研发,适用…...
C++通用算法
1.概述根据名字就知道如何使用相关算法,比如copy函数,就是复制的意思,它需要一个范围,以及要复制的位置copy(begin, end, container_begin);#include <iostream> #include<vector> #include<algorithm> #includ…...
Springboot停机方式
1. 介绍 简单的说,就是向应用进程发出停止指令之后,能保证正在执行的业务操作不受影响,直到操作运行完毕之后再停止服务。应用程序接收到停止指令之后,会进行如下操作: 1.停止接收新的访问请求 2.正在处理的请求&…...
如何将Claude Code的配置无缝迁移至Taotoken平台以解决封号困扰
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 如何将Claude Code的配置无缝迁移至Taotoken平台以解决封号困扰 Claude Code 作为一款高效的编程助手,其核心能力依赖于…...
Docker 的了解和使用
1. 虚拟化全虚拟化:虚拟机的操作系统可以和宿主机的操作系统完全不同。os层虚拟化:操作内核相同,软件虚拟化。2. docker安装 Docker容器本质上是Linux容器,它需要Linux内核环境才能运行。在Windows上直接运行Docker,需…...
开源密钥管理器VSV:一个加密文件搞定多环境密钥管理
1. 项目概述:一个面向开发者的加密密钥管理器最近在折腾一个内部项目,需要管理不同环境(开发、测试、生产)的数据库密码、API密钥这些敏感信息。一开始图省事,直接写在了.env文件里,结果在代码评审时被同事…...
动物森友会岛屿设计终极指南:用Happy Island Designer轻松规划你的梦想岛屿
动物森友会岛屿设计终极指南:用Happy Island Designer轻松规划你的梦想岛屿 【免费下载链接】HappyIslandDesigner "Happy Island Designer (Alpha)",是一个在线工具,它允许用户设计和定制自己的岛屿。这个工具是受游戏《动物森友会…...
揭秘AI教材生成秘诀!AI教材写作工具助力,低查重完成20万字教材!
教材编写难题与AI工具解决方案 在编写教材时,如何才能精准满足不同的需求呢?不同学段的学生在认知能力上存在显著差异,内容过于复杂或简单都不合适;而在课堂教学和自主学习等不同场景下,对教材的要求又各不相同&#…...
英特尔转型芯片代工:从IDM巨头到服务商的六大挑战与机遇
1. 英特尔代工之路:从IDM巨头到服务提供商的六大挑战在半导体行业,英特尔这个名字几乎就是高性能微处理器的代名词。这家公司凭借其垂直整合制造模式,在过去几十年里构筑了难以撼动的技术护城河。然而,当行业的目光从单纯的制程竞…...
斐讯K3从梅林‘变砖’到官复原职:一个手残党的硬核救砖全记录(附TTL/编程器操作避坑点)
斐讯K3救砖实战:从梅林固件崩溃到完美恢复的完整指南 1. 当路由器变成"砖头":一个普通用户的崩溃瞬间 那是一个普通的周末下午,我正兴冲冲地准备给我的斐讯K3刷上梅林固件,幻想着能获得更强大的功能和更稳定的性能。按照…...
Jellyfin智能片头检测解决方案:Intro Skipper插件技术指南
Jellyfin智能片头检测解决方案:Intro Skipper插件技术指南 【免费下载链接】intro-skipper Fingerprint audio to automatically detect and skip intro sequences in Jellyfin 项目地址: https://gitcode.com/gh_mirrors/in/intro-skipper Intro Skipper是一…...
如何在10分钟内完成1小时视频硬字幕提取:望言OCR完整指南
如何在10分钟内完成1小时视频硬字幕提取:望言OCR完整指南 【免费下载链接】SubtitleOCR 快如闪电的硬字幕提取工具。仅需苹果M1芯片或英伟达3060显卡即可达到10倍速提取。A very fast tool for video hardcode subtitle extraction 项目地址: https://gitcode.com…...
管式土壤墒情监测站:深埋地下测湿度,云端上报助灌溉
管式土壤墒情监测站采用土壤介电常数检测原理,结合专业数学模型算法,搭配独创螺旋式测量电极结构开展高精度土壤含水率监测。土壤介电常数与土壤含水量存在稳定且精准的对应关系,设备通过传感器高频感知土层介电参数变化,经内置算…...
