【线段】

题目描述

给出一个长度为 M 的正整数序列 A[1],A[2],…,A[M-1],A[M],求有多少个不同的二元组 (K,L) (K<=L) ,满足 (A[K]+A[K+1]+…+A[L]) mod M = 0 。

输入格式

第一行一个数 M 表示序列长度。
第二行 M 个正整数,用空格隔开。

输出格式

输出满足条件的二元组 (K,L) 的个数。

样例数据 1

输入

2
10 1

输出

1

备注

【数据范围】
30%:M<=1000。
100%:M<=100000,0<A[i]<=10^9,保证最终的结果在 long int 范围内。

求出前缀和如果对m取模的值相等那么这两个前缀和相减模m一定为0,记录一下每个前缀膜m的余数以余数作为数组下标统计出现次数即可,然后答案直接就出来了……

下面是代码:

 

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*