一.

题目描述：给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。你能求出数列中总共有多少个 K 倍区间吗？

结论：求区间和，可以通过前缀和来求出。sum[r]−sum[l−1]就是区间[l,r]的和。如果区间[l,r]的和是k的倍数则有(sum[r]−sum[l−1])%k==0，即sum[r]%k==sum[r]%k。因此，我们可以得到一个结论，对前缀和取模之后，两个相等的前缀和就能组成一个k倍区间。

思考：有了这个结论之后，我们就可以使用两层for循环来计数k倍区间的个数，但是由于数据比较大，我们不能这样做。那么我们能不能在计算前缀和的过程中同时来统计k倍区间的个数呢？当然可以。我们可以用一个数组cnt，规定cnt[i]表示当前位置之前，前缀和取模后等于i的个数，以后每出现一次前缀和（取模后）和它相等，那么k倍区间就加上cnt[sum[i]]，然后cnt[sum[i]]++。这样似乎不容易理解，我们用样例举个例子。

对于数列 1 2 3 4 5，k = 2

对前1个数的和模k后为1，在此之前有0个前缀和取模后为1，总个数+0

对前2个数的和模k后为1，在此之前有1个前缀和取模后为1，总个数+1

对前3个数的和模k后为0，在此之前有0个前缀和取模后为0, 总个数+0

对前4个数的和模k后为0，在此之前有1个前缀和取模后为0，总个数+1

对前5个数的和模k后为1，在此之前有2个前缀和取模后为1，总个数+2

但是我们还忽略了一点，就是我们这样做我们少计算了区间[0,i][0,i]构成的k倍区间，其个数为cnt[0]。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
#define sc(n) scanf("%d",&n)
#define print(n) printf("%d\n",n)
#define endl "\n";
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int N=1000010,P=131;
const int MOD = 1e9 + 7;
const int INF=1e9;
const double eps=1e-5;

int n,m,k;
int a[N],b[N],sum[N],res[N];

int main(){
    sc(n);
    sc(k);
    ll ans=0;
    sum[0]=0;
    for(int i=1;i<=n;i++){
        cin>>m;
        sum[i]=(sum[i-1]+m)%k;
        ans+=res[sum[i]];//ans答案爆long long ;之前有出现取模后相同的答案就加上
        res[sum[i]]++;
    }
    cout<<ans+res[0]<<endl;
    return 0;
}
/*
*/

二

小圆的数组

和上面类似：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> q[100005];//前缀和模k为i的值存在q[i]
int n,k,z;
ll a[100005];
int solove(ll x){
    int p = x % k;
    int res = upper_bound(q[p].begin(),q[p].end(), x-z) - q[p].begin();//找到x-q[i]>=z的个数
    q[p].push_back(x);
    return res;
}
int main(){
    scanf("%d%d%d",&n,&k,&z);
    q[0].push_back(0);//模k等于0算自己
    for(int i = 1 ; i <= n ; ++i){
        scanf("%lld",a+i);
        a[i] += a[i-1];
    }
    int ans = 0;
   for(int i = 1 ; i <= n ; ++i){
       ans += solove(a[i]);
   }
    printf("%d\n",ans);
}