题解：CF2276C Subarrays

Auroral__ · 2026-10-21 20:29:33 · 题解

题目大意

给定 T 组数据，每组数据给出一个数组长度 n，和一个 k，一个数组 a，询问数组 a 中有多少个平衡子数组。

平衡子数组满足的条件：

1. 子数组中元素和能被 k 整除。
2. 子数组中元素的个数大于 k。

解题思路

用 s_{i} 表示 1 到 i 每个元素的和，通过平衡子数组的定义第一条可以推出 s_{r} - s_{l-1}\equiv0\pmod{k}，则 s_{r}\equiv s_{l-1}\pmod{k}。

那平衡子数组定义的第二条中，用 len 表示子数组的长度，则 len=r-l+1，因为 len>k 则 r-l+1>k，即 l\le r-k。

代码

#include<bits/stdc++.h>
using namespace std;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n,k,a[200005],ans=0;
        cin>>n>>k;
        vector<int> q(k,0),s(n+5);
        for(int i=1;i<=n;i++) cin>>a[i],s[i]=(s[i-1]+a[i])%k;
        for(int i=1;i<=n;i++){
            int l=i-k-1;
            if(l>=0) q[s[l]]++;//记录每个余数出现的次数
            ans+=q[s[i]];
        }cout<<ans<<"\n";
    }
    return 0;
}