自动搬运

查看原文

来自洛谷，原作者为

	Steve_xh 舍而后得。

搬运于2025-08-24 22:41:04，当前版本为作者最后更新于2023-04-26 13:19:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Update 2024/12/4：修改了部分表述不太清楚的点。

Update 2025/7/12：考虑到大多数做本题的都是初学者，优化了表述。

题意

题目传送门

题目大意：

给定长度为 $n$ 的一段序列 $a$，求此序列中有多少子区间和为 $k$ 的倍数。

思路

首先，我们看到题目中出现了连续子序列的和，这启发我们想到前缀和，因为使用它一般可以很方便地求出一段序列的某个连续子序列的和。

因此，我们先把 $a$ 的前缀和求出来。这里设 $S_i$ 为 $a_i$ 的前缀和，即 $S_i=a_1+a_2+\dots+a_i$。

但是仅仅知道了区间和也没有用，题目中还要求区间和是 $k$ 的倍数。这意味着，这段区间的和对 $k$ 取模的结果为 $0$。

不妨把区间表示出来，假设现在的区间是 $[l,r]$，那么该段区间的和就是 $(S_r-S_{l-1})$。由于区间和对 $k$ 取模为 $0$，我们知道

由同余式的性质，上式即

也就是说，这两个前缀和对 $k$ 取模的结果是相等的，即这两个前缀和在模 $k$ 意义下同余。很容易发现 $l-1<r$，也就是说当我们顺序遍历整个前缀和时，式子右边的 $S_{l-1}$ 会先出现。相应地，$S_{l-1}\bmod k$ 也会先出现。这就启发我们去记录每个前缀和对 $k$ 取模的结果，并统计各个结果的出现次数。

统计了有什么用呢？假设我们现在到了第 $i$ 个位置，对于一个 $j<i$，如果我们知道 $S_j$ 对 $k$ 取模的结果与 $S_i$ 对 $k$ 取模的结果是相同的，那么这样的 $(j,i)$ 对子就相当于我们之前的 $(l-1,r)$，可以确定区间和 $(a_l+\dots+a_r)$ 就是 $k$ 的倍数。

如果我们知道了这样的 $j$ 的数量，那么每一个 $j$ 都可以和 $i$ 匹配组成一段区间，相应的我们就可以知道以 $i$ 为右端点的区间数量，就能把答案统计上了。

当然需要注意的是，我们现在的 $j$ 对应的是 $(l-1)$，同时 $i$ 对应的是 $r$。而 $l$ 的范围是 $[1,r]$，相应的 $(l-1)$ 的范围就是 $[0,r-1]$，所以在代码中我们的循环要从 $0$ 开始。

代码

#include<bits/stdc++.h>
#define int long long //一定要开long long
using namespace std;
int n,k,s[100005],ans=0,b[100005];//s前缀和数组，b用于存储前缀和的模数
signed main(){
    cin>>n>>k;
    for(int i=1,t;i<=n;i++)
        cin>>t,s[i]=s[i-1]+t; //输入并计算前缀和
    for(int i=0;i<=n;i++)//注意！必须从0开始，因为0的位置也能和后面的下标构成满足条件的子序列
        ans+=b[s[i]%k]++;//统计答案的同时也要加上当前余数，方便为以后的i服务
    cout<<ans;
    return 0;
}