AtCoder Beginner Contest 146_E - Rem of Sum is Num

本文主要是介绍AtCoder Beginner Contest 146_E - Rem of Sum is Num，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

预处理即可
我们要找的是 (f[i] - f[j]) % k == i - j
移项可得 f[i] - i = f[j] - j 在 i - j <= k 的条件下
因此题目变成了，对于每个右端点，在它的左边 k - 1 个有多少个满足 f[i] - i = f[j] - j
f[i] 是前缀和数组
AC_CODE

#include <map>
#include <iostream>
#define LL long long

using namespace std;

const int N = 2e5 + 10;

LL f[N];
map<LL, int> mp;
LL ans;
int main() {
    
    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) {
        cin >> f[i]; f[i] += f[i - 1];
    }
    for(int i = 1; i <= n; i ++ )   
        f[i] = (f[i] - i) % k;
    int idx = min(n, k - 1);
    for(int i = 0; i <= idx; i ++ ) {
        ans += mp[f[i]];
        mp[f[i]] ++;
        // cout << ans << endl;
    }
    for(int i = idx + 1; i <= n; i ++ ) {
        mp[f[i - k]] --;
        ans += mp[f[i]];
        mp[f[i]] ++;
    }
    cout << ans << endl;
    return 0;
}

这篇关于AtCoder Beginner Contest 146_E - Rem of Sum is Num的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！