第八届蓝桥杯 Java B——k 倍区间

给定一个长度为 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);
    }
}