摘桃子（推式子+优化）

题目链接：摘桃子
题意：有n个数，选连续x个数，如果这些数的和对k取模后的结果也是x，那么算是一种方案。求总方案数是多少。
没啥思路，由于以前这种题大多数是推推式子，对着式子展开思路，我也就推了推式子。
条件是这样的，对于（L，R）有：
R - （L - 1） >= k - 1
（sum（R）- sum（L - 1））% k = R - （L - 1）
那么就有 sum（R）- R = sum（L - 1） - （L - 1）+ k的倍数。
即对于每个sum ( i )，找有多少 sum ( j ) - sum ( i - 1 ) 是 k 的倍数，相减为k的倍数，那么取模后相等，所以有转化成了，对于 sum (i - 1) %k，找区间内有多少个数相等。这时候用map当桶就简单了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 1e9 + 7;
int sum[N];
unordered_map<int, int> mp;
signed main()
{
    
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
    
        int x;
        scanf("%lld", &x);
        sum[i] = sum[i - 1] + x;
    }
    for (int i = 1; i <= n; i++) {
    
        sum[i] -= i;
        sum[i] = ((sum[i] % k) + k) % k;
    }
    for (int i = 1; i <= min(k - 1, n); i++) mp[sum[i]]++;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
    
        int x = sum[i - 1];
        ans += mp[x];
        mp[sum[i]]--;
        int r = i + k - 1;
        if (r <= n) mp[sum[r]]++;
    }
    cout << ans;
    return 0;
}