解题思路

要统计所有长度为 K 的连续区间的和是不是 m 的倍数。如果每个区间都重新加一遍，当 n 很大（最大 50 万）时会超时，所以用滑动窗口：

1. 先算出第一个长度为 K 的窗口和。
2. 窗口每次向右滑一格：加上新进来的数、减掉离开窗口的数，就得到下一个窗口和。

这样每个窗口只需 O(1) 更新，总复杂度 O(n)。

参考代码

#include <cstdio>
#include <iostream>
using namespace std;

int a[500005];

int main() {
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    long long sum = 0;
    int cnt = 0;
    // 第一个长度为k的窗口
    for (int i = 0; i < k; i++) sum += a[i];
    if (sum % m == 0) cnt++;
    // 窗口向右滑动：加进新数，去掉旧数
    for (int i = k; i < n; i++) {
        sum += a[i] - a[i - k];
        if (sum % m == 0) cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

复杂度分析

每个数只处理一次，时间复杂度 O(n)，额外空间复杂度 O(n)。