题目描述

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

输出格式
输出一个整数，代表 K 倍区间的数目。

数据范围
1≤N,K≤100000,
1≤Ai≤100000

输入样例：
5 2
1
2
3
4
5

输出样例：
6

问题分析

首先区间和，大家很容易想到前缀和所以这一点无需讨论
接下来就是对于区间k倍的求解了
对于前缀和
num[i]%k = a
(num[i]-num[j])%k = num[i]%k-num[j]%k
由题意前者值为零
那么num[i]%k == num[j]%k
所以是不是只要左右区间端点余数相同 就能被k整除呢
当然还有一点
其次对于余数为零的端点（0，i）本身就能被整除
这样整体的解决方法就有了，只要两个点余数相同就是k倍区间了
那接下来我们假设一下
如果 这里有三个端点余数相同会怎么样呢
我们想一下，一个区间是不是有两个端点
所以对于余数相同的n个点我们是不是要选两个点
C（n，2
问题一下就变成了组合数问题

那么接下来我们汇总一下
1。两个端点余数相同，则能被整除，因此我们对前缀和序列进行求余直接获得余数
2.余数为零的端点本身就是k倍区间
3.对于相同余数的n个端点，我们每次选两个
所以对于余数i的区间我们可以有个区间
同时我们可以记录一下余数的个数，这样直接On求组合数
（4.根据前面的我又做了一个优化 n个数字则最多会有C(n,2)的区间
所以我们打表初始化一下0~n的组合数）

时间复杂度

O(n)

C++ 代码

#include <iostream>
using namespace std;
long long num[100000],n,k,Data,in,count,result[100000];

int main(){
    cin>>n>>k;
    Data = 0;
    result[0] = result[1] = 0;
    result[2] = 1;
    for(int i=3;i<=n;i++){
        result[i] = (result[i-1]*i)/(i-2);
    }
    while(n--){
        cin>>in;
        Data+=(in%k);
        Data%=k;
        num[Data]++;
        //cout<<Data<<endl;
        if(!Data){
            count++;
        }
    }
    //cout<<count<<endl<<endl;
    for(long long i =0;i<k;i++)
    {
        count+=result[num[i]];
        //cout<<i<<" "<<combine(i)<<endl<<endl;
    }
    cout<<count;
    return 0;
}