一个人的巴黎

用户名：uq_36478041918

访问量：14980

签　名：

等　　级
排　　名	105
经　　验	8303
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

蓝桥杯历届试题-小朋友排队【树状数组 C++ 详解】
浏览：996

信息学奥赛一本通T1425-加工生产调度(贪心算法)
浏览：552

蓝桥杯2017年第八届真题-包子凑数【拓展欧几里得完全背包】
浏览：267

你可能喜欢

蓝桥杯2017年第八届真题-k倍区间【前缀和+数学优化】

　　作者: 一个人的巴黎　　　　发表时间：2022-04-04 15:26:11 浏览：241　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-k倍区间

最先想到的应该是静态的前缀和，利用前缀和求区间和：
不多说了，比较简单，就是求Ai~Aj的和
```cpp
#include<iostream>
using namespace std;
int n,k;
int A[100001];
int sum[100001];
int cnt=0;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>A[i];
		sum[i]=sum[i-1]+A[i]; 
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			if((sum[j]-sum[i-1])%k==0)
				cnt++;
		}
	}	
	cout<<cnt<<endl;
	return 0;
}
```
但是会超时，部分case通不过，原因：复杂度O(n²)=( `$$10^{5}$$`)²=`$$10^{10}$$`
下面用数学进行优化，在计算前缀和时，将前缀和%k,计算同余的数量
每一种余数中任取两个，这两个数分别作为区间的头和尾，这段区间和一定%k==0
就像钟表，对于钟表，他的k为12，你1点%12==1，你13点%12==1，你25点%12==1(次日1点),只不过是多转了几圈的问题，一圈就是12，那你就可以先将1，13，25%12(即k),这三个数中任取两个区间和都为12的倍数，即%12==0。
那么原来的双重循环去找i，j的位置就没有必要了，直接计算`$$C^{2}_{m}$$`
```cpp
#include<iostream>
using namespace std;
int n,k;
int A[100001];
int sum[100001];
int num[100001];
long long cnt=0;
int main(){
	cin>>n>>k;
	num[0]=1;
	for(int i=1;i<=n;i++){
		cin>>A[i];
		sum[i]=(sum[i-1]+A[i])%k;//sum[i]是余数 
		num[sum[i]]++;//余数相同的位置计数 
	}
	for(int i=0;i<k;i++){//枚举所有余数的可能性 
		cnt += (long long)num[i] * (num[i]-1) / 2;//计算C2m，并强制类型转换 
	}
	cout<<cnt<<endl;
	return 0;
}
```

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-温度转换（C语言代码）

回文数字（C++代码）

点我有惊喜！你懂得！

C语言考试练习题_保留字母（C语言代码）

蓝桥杯2017年第八届真题-k倍区间【前缀和+数学优化】

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

不容易系列（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

P1001 （C语言代码）

K-进制数（C语言描述，蓝桥杯）

C二级辅导-同因查找（C语言代码）

找出最长的字符串来（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-等差数列（C语言代码）

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-温度转换 （C语言代码）

回文数字 （C++代码）

点我有惊喜！你懂得！

C语言考试练习题_保留字母 （C语言代码）

蓝桥杯2017年第八届真题-k倍区间【前缀和+数学优化】

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

不容易系列 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

P1001 （C语言代码）

K-进制数 （C语言描述，蓝桥杯）

C二级辅导-同因查找 （C语言代码）

找出最长的字符串来 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-等差数列 （C语言代码）

C二级辅导-温度转换（C语言代码）

回文数字（C++代码）

C语言考试练习题_保留字母（C语言代码）

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

不容易系列（C语言代码）

K-进制数（C语言描述，蓝桥杯）

C二级辅导-同因查找（C语言代码）

找出最长的字符串来（C语言代码）

C二级辅导-等差数列（C语言代码）