AtCoder Beginner Contest 146 E - Rem of Sum is Num(思维)

题目链接
给你一个长度为 $n$n的序列，和一个 $k$k.
询问你有多少个区间 $[l,r]$[l,r]，满足 ${\sum }_{i=l}^r{a}_{i}modk=r-l+1$∑i=lr​ai​  mod  k=r−l+1

我们把题目要求的式子转化一下就是 ${\sum }_{i=l}^r{a}_i-(r-l+1)modk=0$∑i=lr​ai​−(r−l+1)  mod  k=0

那么我们枚举右端点，看每个右端点有几个符合的左端点。
我们先记录前缀和。
然后枚举右端点 $r$r：要找到所有 $l$l满足 ${\sum }_{i=1}^r{a}_i-\left(r\right)\equiv {\sum }_{i=1}^{l-1}{a}_i-(l-1)modk$∑i=1r​ai​−(r)≡∑i=1l−1​ai​−(l−1)  mod  k
那么很显然了， $map$map记录一下每个前缀和-下标出现的次数即可！

注意：因为区间长度必须严格小于 $k$k才满足，所有我们要把超过的部分给去掉！

细节见代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,k,a[N];
LL s[N],t[N];
map<int,int>vis;
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i],s[i]=(s[i]+k)%k;
    LL ans=0;
    vis[0]=1;
    int l=0;
    for(int i=1;i<=n;i++){
        while(i-l>=k){
            vis[(s[l]-l%k+3ll*k)%k]--;//相当于找到一段区间的sum-len=0 (%k )
            l++;
        }
        ans+=vis[(s[i]-i%k+3ll*k)%k];
        vis[(s[i]-i%k+3ll*k)%k]++;
    }
    cout<<ans<<'\n';
    return 0;
}