多多的求和计算

[编程题]多多的求和计算

热度指数：7074 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

多多路上从左到右有N棵树（编号1～N），其中第i个颗树有和谐值Ai。

多多鸡认为，如果一段连续的树，它们的和谐值之和可以被M整除，那么这个区间整体看起来就是和谐的。
现在多多鸡想请你帮忙计算一下，满足和谐条件的区间的数量。

输入描述:

第一行，有2个整数N和M，表示树的数量以及计算和谐值的参数。
（ 1 <= N <= 100,000, 1 <= M <= 100  ）
第二行，有N个整数Ai, 分别表示第i个颗树的和谐值。
（ 0 <= Ai <= 1,000,000,000 ）

输出描述:

共1行，每行1个整数，表示满足整体是和谐的区间的数量。

示例1

输入

5 2
1 2 3 4 5

输出

说明

长度为1: [2], [4]
长度为2: 无
长度为3: [1,2,3], [3,4,5]
长度为4: [1,2,3,4], [2,3,4,5]
长度为5: 无
共6个区间的和谐值之和可以被2整除。

备注:

对于50%的数据，有N<=1,000
对于100%的数据，有N<=100,000

算法知识视频讲解

Python

Bayes305

Python3

n, m = map(int, input().split())
tree = list(map(int, input().split()))
d = {0: 1}
s, r = 0, 0
for i in range(n):
    r = (r + tree[i]) % m
    s += d.get(r, 0)
    d[r] = d.get(r, 0) + 1
print(s)

编辑于 2021-10-29 07:34:02 回复(0)

Python

全力以fu，踏上新征tu

# 利用前缀和原理
n,m = list(map(int, input().strip().split(' '))) # 主要在意M就行，要能被M整除
ai=list(map(int,input().strip().split(' '))) # 每个数组的值
li={0:1} # li字典放所有的前缀和 除 m 得到的余数出现的次数，初始化我们需要 使出现 余数为 0 出现一次
sum=0
count = 0 # 用来统计
for i in ai:
    sum+= i # 前缀和
    yu=sum%m # 求前缀和的除m的余数
    if yu in li.keys():
        # 如果 已有存在的key（余数）说明到他这里我们必有可以除断的。（可以理解为余数一样的那么中间这一段必定可以除断）
        # 然后我们需要看几个余数一样的来判断可以组合几个
        count += li[yu]
    if yu not in li.keys(): # 将前缀和的余数存进字典
        li[yu]=1
    else:
        li[yu]+=1
print(count)

发表于 2021-09-24 10:01:47 回复(0)