P8649 题解

· · 题解

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，我们知道

S_r-S_{l-1}\equiv 0\pmod{k}

由同余式的性质，上式即

S_r\equiv S_{l-1}\pmod{k}

也就是说，这两个前缀和对 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;
}