首页 > 代码库 > 20140710 总结
20140710 总结
今天见到了传说中拥有把妹之手的_ty，orz...
想起了夏令营那段不堪回首(?)的日子....和那个欢快的(没有作业的)暑假.....
今天的题好像很正常的样子...哎!Naive！！！
eagleeggs写了太久然后放弃了，然后就没有把loop写完TAT
然后蠢蠢的把squence的规律推错了....
-----------------------------------------------------------------------------
sequence|sequence.in|sequence.out
题目描述：
给定一个整数K和长为N的数列{Ai}，求有多少个子串（不含空串）的和为K的倍数。（在这里子串表示{A[i]..A[j]}，i<=j）
输入格式：
共两行
第一行 两个整数N,K
第二行 N个整数表示数列{Ai}
输出格式：
一行一个整数 表示满足条件的子串的个数
样例输入：
6 3
1 2 6 3 7 4
样例输出：
7
数据范围：
20% N<=100
对另外20% K<=100
对所有数据 N<=500000 K<=500000
保证输入数据中所有数都能用longint保存
1 #define NOMBRE "sequence" 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int MAXN = 5*1e5+10; 9 10 long long Pri, sum;11 int n, k, a, h[MAXN];12 13 int main(){14 freopen(NOMBRE ".in", "r", stdin);15 freopen(NOMBRE ".out", "w", stdout);16 17 memset(h, 0, sizeof(h));18 19 scanf("%d %d", &n, &k), sum = Pri = 0, h[0] = 1;20 for (register int i=1; i<=n; i++){21 scanf("%d", &a);22 sum = (sum+a)%k;23 while (sum<0) sum += k;24 Pri += h[sum] ++;25 }26 printf("%I64d\n", Pri);27 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。