算法
(数论、计数、思维) $O(N\log N)$
记 $S_k = \sum\limits_{i=1}^k A_i$
题目其实就是问有多少对 $(l, r)$ 满足 $(S_r - S_{l-1}) \% K = r - l + 1$,这等价于 $(S_r - r) - (S_{l-1} - (l - 1)) \equiv 0 \pmod K$ 等价于 $S_r - r \equiv S_{l-1} - (l - 1) \pmod K$
对于其中减去数组下标这个操作,我们可以提前对 $A_i$ 减掉 $1$ 来实现
这样就变成了 $S_r \equiv S_{l-1} \pmod K$,做法同 ABC105D ,(为了方便,我们可以提前对 $S_i$ 模掉 $K$),只需用 std::map
来统计 $S_i$ 的个数,$S_i$ 对答案的贡献为在第 $i$ 个元素之前和 $S_i$ 相等的元素个数
然后注意到,合法的区间长度大于 $0$ 且不超过 $K - 1$,所以我们可以维护一个队列,依次将 $S_i$ 压入队列,若队列中的元素个数达到 $K$ 时,把队头元素的个数减一,并将队头元素弹出。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::map;
using std::vector;
using std::queue;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
rep(i, n) a[i]--;
vector<int> s(n+1);
rep(i, n) {
s[i+1] = (s[i] + a[i]) % k;
}
map<int, int> mp;
ll ans = 0;
queue<int> q;
rep(j, n + 1) {
ans += mp[s[j]];
mp[s[j]]++;
q.push(s[j]);
if (q.size() == k) {
mp[q.front()]--;
q.pop();
}
}
cout << ans << '\n';
return 0;
}
完蛋,这个公式推导没看懂QAQ
就是把 $r-l+1$ 移到左边
太牛了,大佬这个把$A[i] - 1$然后就 简化了 QAQ