前言
简单题，whk 的时候就秒了，但是不知道为什么很喜欢这题，就来写题解啦！
（还有一个原因是，现有题解都不知道在讲啥东西。）
思路
区间求和，容易想到前缀和。题目等价于，有多少个 \(sum_r - sum_{l-1} \equiv r-l+1 \pmod k\)。
比较有趣的是移项，右边的都移到左边去，发现等价于求 \((sum_r - r) - \Big(sum_{l-1} - (l-1)\Big) \equiv 0 \pmod k\)。
所以维护 \(val_i=(sum_i - i)\mod k\) 是否相同就完事了，上 map。
代码
细节有两个：
- 注意算上 \(val_0\)，因为 \((l-1)\) 可能跑到 \(0\) 去。
- 超出区间范围要剔除。
#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;
int val[200005];
unordered_map <int, int> cnt;
int main()
{
int n, k;
scanf("%d%d", &n, &k);
long long ans = 0, sum = 0;
val[0] = 0, cnt[0]++;
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x), x %= k, sum += x;
val[i] = ((sum - i) % k + k) % k;
if (i >= k) cnt[val[i - k]]--;
ans += cnt[val[i]], cnt[val[i]]++;
}
cout << ans;
return 0;
}
希望能帮助到大家！