P8649 [蓝桥杯 2017 省 B] k 倍区间:同余，前缀和，组合数，区间个数

题目描述

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

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

输入格式

第一行包含两个整数 NN 和 KK(1≤N,K≤105)(1≤N,K≤105)。

以下 NN 行每行包含一个整数 AiAi​(1≤Ai≤105)(1≤Ai​≤105)。

输出格式

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

输入输出样例

输入 #1复制

5 2
1  
2  
3  
4  
5  

输出 #1复制

6

说明/提示

时限 2 秒, 256M。蓝桥杯 2017 年第八届

做法

这题我们用前缀和来写，暴力做法是对于每个右端点，枚举每个左端点，符合的区间就加一，当然，这太暴力了。我们求区间个数一般都是先遍历右端点，然后左端点个数 O(1) 就能求出来了,就是直接查询。

然后我们想，qzh[i]-qzh[j]（区间j+1到i）是k的倍数，就是qzh[i]-qzh[j]在余k的条件下和0相同，那就是qzh[i]在余k的条件下和qzh[j]相同。那么，我们枚举右端点，只要有和它的余数相同的，就是符合的左端点。但是这样复杂度并没有降下去。

其实正确做法是，我们知道了0到k-1的每个余数的个数，那么我们就从中选两个，有多少种组合，就有多少个区间。这就用到了组合数。

有一个特殊情况，当余数是0时，单个也是符合条件的，所以要再加上余数是0的个数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,k,sum,ans;
map<int,int> mp;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){cin>>a;sum+=a%k;sum%=k;mp[sum]++;}for(int i=0;i<k;i++){if(i==0) ans+=mp[i]*(mp[i]-1)/2+mp[i];else{ans+=mp[i]*(mp[i]-1)/2;}}cout<<ans;}