蓝桥杯练习题--k倍区间（前缀和+组合数学）

1230: k倍区间

时间限制: 1 Sec   内存限制: 128 MB
提交: 73   解决: 17
[ 提交][ 状态][ 讨论版]

题目描述

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

输入

第一行包含两个整数N和K。(1 <= N, K <= 100000)  
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000) 

输出

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

样例输入

5 2

1  

2  

3  

4  

5  

样例输出

6

这是道看着挺难，实际并不困难的水题（-_-||），首先可计算出前缀和数组sum，题意要求(sum[i]-sum[j])%k==0,将这个式子化简一下，可得sum[i]%k==sum[j]%k,则问题可转换为有多少个sum[i]%k的值相同，用组合数学求一下即可，但也要注意取余值为零的情况，要额外加上。

#include<stdio.h>#include <algorithm>#include<iostream>#include<string.h>#include<vector>#include<stdlib.h>#include<math.h>#include<queue>#include<deque>#include<ctype.h>#include<map>#include<set>#include<stack>#include<string>#include<algorithm>#define ll long long#define INF 0x3f3f3f3f#define FAST_IO ios::sync_with_stdio(false)using namespace std;ll a[100005],aa[100005],vis[100005];int main(){    int n,k;    cin>>n>>k;    for(int i=1;i<=n;i++)    {        cin>>a[i];        aa[i]=aa[i-1]+a[i];        vis[aa[i]%k]++;    }    ll ans=0;    for(int i=0;i<k;i++)    {        ans+=(vis[i]*(vis[i]-1))/2;        if(i==0)            ans+=vis[i];    }    cout<<ans<<endl;    return 0;}