没有备案的网站怎么访问,互动网站,辽宁网站建设招标,常德网站制作公司题目描述
给定一个长度为 NN 的数列#xff0c;A1,A2,⋯ANA1,A2,⋯AN#xff0c;如果其中一段连续的子序列 Ai,Ai1,⋯Aj(i≤j)Ai,Ai1,⋯Aj(i≤j) 之和是 KK 的倍数#xff0c;我们就称这个区间 [i,j][i,j] 是 KK 倍区间。
你能求出数列中总共有多少个 KK 倍区…题目描述
给定一个长度为 NN 的数列A1,A2,⋯ANA1,A2,⋯AN如果其中一段连续的子序列 Ai,Ai1,⋯Aj(i≤j)Ai,Ai1,⋯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]区间j1到i是k的倍数就是qzh[i]-qzh[j]在余k的条件下和0相同那就是qzh[i]在余k的条件下和qzh[j]相同。那么我们枚举右端点只要有和它的余数相同的就是符合的左端点。但是这样复杂度并没有降下去。
其实正确做法是我们知道了0到k-1的每个余数的个数那么我们就从中选两个有多少种组合就有多少个区间。这就用到了组合数。
有一个特殊情况当余数是0时单个也是符合条件的所以要再加上余数是0的个数。
#includebits/stdc.h
#define int long long
using namespace std;
int n,a,k,sum,ans;
mapint,int mp;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cinnk;for(int i1;in;i){cina;suma%k;sum%k;mp[sum];}for(int i0;ik;i){if(i0) ansmp[i]*(mp[i]-1)/2mp[i];else{ansmp[i]*(mp[i]-1)/2;}}coutans;}
