解题思路:如果把所有区间分为k倍区间和非k倍区间,观察一下他们之间的区别,k倍区间的和modk后等于0,而非k倍区间的和modk后等于n,n是介于1至k-1的数.再来思考一下如何得到k倍区间,第一种情况,本身就是k倍区间,不那么用做任何操作,第二种情况,本身是非k倍区间,我们需要通过组合两个(为什么是两个,不是多个呢?请读者自行思考,才能理解算法过程)连续(包含关系)的非k倍区间,来消除n的影响,那么两区间之间部分就成为k倍区间.
注意事项:我是用C++AC的,时间复杂度在O(n)下,python都会超时,题解仅提供python的写法,便于理解
参考代码:
n, k = map(int, input().strip().split()) modk = [0 for i in range(k)] prefix = 0 #前缀和 count = 0 for i in range(n): temp = int(input().strip()) prefix += temp modk[prefix % k] += 1 # 统计前缀和modk结果相同的区间数,即同类非k倍区间,同类是为了消除n的影响 for j in range(k): count += modk[j] * (modk[j] - 1) // 2 # 等差数列求和公式,或者C(n,2)组合 count += modk[0]#本身就是k倍区间无需组合 print(count)
0.0分
1 人评分
C二级辅导-等差数列 (C语言代码)浏览:1214 |
C语言训练-排序问题<2> (C++代码)浏览:880 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:578 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:994 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:640 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:372 |
打印十字图 (C语言代码)浏览:2701 |
核桃的数量 (C语言代码)浏览:870 |
C二级辅导-求偶数和 (C语言代码)浏览:671 |
整除问题 (C语言代码)浏览:519 |