当前位置: 首页 > 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;}

http://www.lryc.cn/news/482332.html

相关文章:

  • 产业与学术相互促进,2024年OEG海上能源博览会助力全球能源可持续发展
  • 【GDB调试】智慧中控项目的调试
  • 《一本书讲透 Elasticsearch》京东评论采集+存储+可视化全 AI 实现
  • uniapp中webview全屏不显示导航栏解决方案
  • Dear ImGui 使用VS2022编译为静态库
  • 5G 现网信令参数学习(3) - RrcSetup(1)
  • PHP实现身份证OCR识别API接口
  • 关于 Qt+Osg中使用背景图HUD受到后绘制几何图形顶点颜色影响 的解决方法
  • [CKS] K8S AppArmor Set Up
  • redis笔记-数据结构
  • webpack的常见配置
  • text-embedding-ada-002;BGE模型;M3E模型是Moka Massive Mixed Embedding;BERT
  • WebRTC 环境搭建
  • FastHTML快速入门:http方法,CSS文件和内联样式,其他静态媒体文件位置
  • 项目管理和研发管理中的痛点及其解决方案
  • 机器学习(基础1)
  • 我谈维纳(Wiener)复原滤波器
  • 怎么看真假国企啊?怎么识别假冒国企的千层套路?
  • C#中break和continue的区别?
  • Linux部署nginx访问文件403
  • 华为OD机试 - 数字排列 - 深度优先搜索dfs算法(Python/JS/C/C++ 2024 C卷 200分)
  • Scrapy爬取heima论坛所有页面内容并保存到数据库中
  • Kafka参数了解
  • sql专题 之 where和join on
  • day12:版本控制器
  • 第四十一章 Vue之初识VueX
  • GIT的基本使用与进阶
  • 【Linux系统】—— 基本指令(二)
  • MFC工控项目实例三十实现一个简单的流程
  • 【Android、IOS、Flutter、鸿蒙、ReactNative 】文本点击事件