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;
}原文地址：https://blog.csdn.net/2301_80718054/article/details/143694563
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！