重庆网站seo按天计费,做网站万网,网站建设 dw,门户网站模板源码题目描述
给定一个长度为 N 的数列#xff0c;A1, A2,…AN#xff0c;如果其中一段连续的子序列 Ai,Ai1⋯Aj ( i ≤j ) 之和是 K 的倍数#xff0c;我们就称这个区间 [i, j]是 K 倍区间。
你能求出数列中总共有多少个 K倍区间吗#xff1f;
输入描述
第一行包含两个…题目描述
给定一个长度为 N 的数列A1, A2,…AN如果其中一段连续的子序列 Ai,Ai1⋯Aj ( i ≤j ) 之和是 K 的倍数我们就称这个区间 [i, j]是 K 倍区间。
你能求出数列中总共有多少个 K倍区间吗
输入描述
第一行包含两个整数 N 和 K( 1≤N,K≤100000 )
以下 N 行每行包含一个整数 Ai ( 1≤Ai≤100000 )
输出描述
输出一个整数代表 K 倍区间的数目
输入输出样例
示例 输入 5 2
1
2
3
4
5输出 6运行限制
最大运行时间2s最大运行内存: 256M
题解 方法一 首先最普遍的方法是暴力算法不停的遍历通过条件判断进行计数。 #inlcudebits/stdc.h
using namespace std;
int n, k;
int a[100000];
int result 0;
int main()
{cin n k;for(int i0; in; i){cin a[i];}for(int i0; in; i){if(a[i] % k 0){result;}for(int ji1; jn; j){a[i] a[i] a[j];if(a[i] % k 0){result;}}}cout result;return 0;
}但是该方法的时间复杂度较高两层for循环O(n*n) 方法二 利用前缀和算法实现前缀和就是数组的前 i 项之和。 假设n5, k2。 则数组a[] {1, 2, 3, 4, 5}的前置和为 原数列12345 前缀和1361015 针对该前缀和对k进行取余 取余后11001 余数相同的两个元素之间的区间即为K倍区间例如mod[2]mod[5]则区间[i1, j]也就是[3,5]是K倍区间。也可以这么理解区间(2,5]为K倍区间该区间左开右闭。 这个理解后就可以认为余数相同的两个数之间的区间即为K倍区间。因此对相同余数的两个元素进行排列组合。为C2 2加上C3 23为下标2为上标结果为134 但是由于该区间是左开右闭的因此要加上取余为0的个数。才构成完整的结果。 也就是先通过排列组合计算出中间区间为K倍区间的个数4个 234534524 再加上取余为0的个数2个 1231234 实际结果为6个。 #include iostream
#include bits/stdc.h
using namespace std;
long long input[100000], mod[100000] {0};
long long add[100000] {0}, sum 0;
int main()
{// 请在此输入您的代码int n, k;long long reslut 0;cin n k;//输入数列for(int i 0; i n; i){cin input[i];}//对数列每个元素求前缀和存入sum并对k进行取余存入modfor(int i 0; i n; i){// 当前索引的前缀和sum input[i];// 对该前缀和对k进行取余mod[i] sum % k;// 对该索引前缀和取余后的数值出现次数进行累加add[mod[i]];}//计算结果for(int i 0; i n; i){// 针对每种取余的值进行计算排列组合最后相加reslut add[i] * (add[i]-1) / 2;}// 由于上面是左开右闭区间缺少了一部分cout reslut add[0] endl;return 0;
}
