首页 > 代码库 > 数列（NOIP17提高模拟训练11）
数列（NOIP17提高模拟训练11）
给你一个长度为N的正整数序列，如果一个连续的子序列，子序列的和能够被K整
除，那么就视此子序列合法，求原序列包括多少个合法的连续子序列？
对于一个长度为8的序列,K=4的情况：2, 1, 2, 1, 1, 2, 1, 2 。它的答案为6，子序列
是位置1->位置8,2->4,2->7,3->5,4->6,5->7。
输入格式：
第一行：T，表示数据组数
对于每组数据：
第一行:2个数，K，N
第二行：N个数，表示这个序列
输出格式：
共T行，每行一个数表示答案
样例输入：
27 31 2 34 82 1 2 1 1 2 1 2
样例输出：
06
数据范围：
100%数据满足
1<=T<=20
1<=N<=50000
1<=K<=1000000
序列的每个数<=1000000000
30%数据满足
1<=T<=10
1<=N,K<=1000
和上次写的思路是一样的，这里不多阐述~
include<bits/stdc++.h>using namespace std; int book[2301000]; int main(){ int t; ios::sync_with_stdio(false); cin>>t; while(t--) { long long k,n; memset(book,0,sizeof(book)); cin>>k>>n; long long sum=0; long long x; long long ans=0; for(int i=1;i<=n;i++) { cin>>x; sum=(sum+x)%k; book[sum%k]++; } for(int i=0;i<=k-1;i++) ans+=book[i]*(book[i]-1)/2; cout<<ans+book[0]<<endl; } return 0;}
数列（NOIP17提高模拟训练11）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。