给定一个长度为N的数列,A1, A2, ... AN,如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗?
输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出
输出一个整数,代表K倍区间的数目。
例如,
输入:
5 2
1
2
3
4
5
程序应该输出:
6
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms
用前缀和来维护区间和信息,然后将前缀和数组中的每个元素都对$k$取模,这样前缀和数组中就会变成一系列值为$0~k-1$的元素,最后统计同一值的元素有多少个,利用组合数学的方法就能求得答案
上面是比较抽象的思路,这里给出具体的例子,假如前缀和数组对$k$取模后,数组内的元素分别为$2,1,1,2,2$,那么下标$1,3,4$两两组合得到区间和$sum[4]-sum[1],sum[4]-sum[3],sum[4]-sum[1]$,这些区间的和一定是k的倍数。
证明很简单,自己动手写一写就知道了,这里不再赘述
import java.io.BufferedInputStream; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream(System.in)); int n = cin.nextInt(); int k = cin.nextInt(); int[] cnt = new int[k]; int[] sum = new int[n + 1]; sum[0] = 0; cnt[0] = 1; for (int i = 1; i <= n; i++) { sum[i] = cin.nextInt(); sum[i] = (sum[i - 1] + sum[i]) % k; cnt[sum[i]]++; } long ans = 0L; for (int i = 0; i < k; i++) // 余数必在0-k-1之间 ans += (long) cnt[i] * (cnt[i] - 1) / 2; System.out.println(ans); } }