题目描述

有 $N$ 个盒子排成一排，第 $i$ 个盒子里有 $A_i$ 个糖果。你需要从一些连续的盒子里取出糖果，分给 $M$ 个小朋友，使得每个小朋友得到的糖果数量相等。求有多少种取法满足以下两个条件：

• 取出的盒子数为 $r-l+1$，其中 $1\le l\le r\le N$。

输入格式

• 第一行包含两个整数 $N$ 和 $M$。
• 第二行包含 $N$ 个整数 $A_1,A_2,\dots ,A_N$。

输出格式

输出一个整数，表示满足条件的取法数。

数据范围

• $1\le N\le 10^5$，
• $1\le M\le 10$，
• $1\le A_i\le 10^9$。

输入样例1：

3 2
4 1 5

输出样例1：

3

样例1解释：

符合条件的取法有 $(1,3),(2,3),(3,3)$。

输入样例2：

13 17
29 7 5 7 9 51 7 13 8 55 42 9 81

输出样例2：

6

输入样例3：

10 400000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出样例3：

25

C++程序

#include <bits/stdc++.h>
using namespace std;
map<long long,int> mp;
long long n,m,x,sum,ans;
int main() {cin >>n >>m;mp[0]=1; // 初始化，表示前缀和为0的出现了1次for (int i=0; i<n; i++) {cin >>x;sum=(sum+x)%m; // 计算前缀和ans+=mp[sum]; // 更新答案mp[sum]++; // 更新前缀和出现次数}cout <<ans;return 0;
}

思路解析

• 首先，我们需要计算出每个位置的前缀和，即前$i$个数的和。然后，我们可以通过计算前缀和的差值，来得到任意一段连续的子数组的和。具体来说，如果我们要求第i到j个数的和，可以用前j个数的前缀和减去前$i-1$个数的前缀和，即：

sum[i, j] = prefix_sum[j] - prefix_sum[i-1]

• 接下来，我们要找到有多少个子数组的和是$M$的倍数。我们可以将所有前缀和对$M$取模，得到一个新的序列。我们要找的就是这个新序列中，有多少个不同的前缀和对$M$取模后的值相同。因为如果两个前缀和对$M$取模后的值相同，那么它们的差值一定是M的倍数，也就是说，它们对应的子数组的和一定是M的倍数。

• 我们可以用一个哈希表来记录每个前缀和对M取模后的值出现的次数。具体来说，我们可以用一个$map<longlong,int>$来表示，其中键是前缀和对$M$取模后的值，值是该值出现的次数。我们可以从左到右遍历所有前缀和，每次遍历到一个前缀和时，我们就在哈希表中查找是否存在一个前缀和对$M$取模后的值，使得当前前缀和减去该前缀和的值是$M$的倍数。如果存在，那么我们就找到了一个符合要求的子数组。具体来说，如果当前前缀和对M取模后的值是$sum$，而之前已经有$cnt$个前缀和对$M$取模后的值是$sum$，那么我们就找到了$cnt$个子数组的和是M的倍数。最后，我们要将当前前缀和对$M$取模后的值出现的次数加$1$，以便后续的查找。

时间复杂度分析

该算法的时间复杂度为$O(n)$，其中$n$为输入的数的个数。因为我们只需要遍历一遍所有前缀和，并且每次查找哈希表的时间复杂度是$O(1)$。空间复杂度为$O(n)$，因为我们需要用一个哈希表来记录每个前缀和对$M$取模后的值出现的次数。