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 
#include 
#define LL long long

using namespace std;

const int N = 2e5 + 10;

LL f[N];
map 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推式子

相关

codeforces和atcoder的思维题目

AtCoder Beginner Contest 218 个人题解

【AtCoder】AGC005 F - Many Easy Problems 排列组合+NTT

AtCoder Beginner Contest 193

AtCoder Beginner Contest 042 题解

AtCoder Regular Contest 133 题解 A - C

AtCoder Beginner Contest 238题解

AtCoder Beginner Contest 233

Atcoder Grand Contest 011&012

AtCoder Grand Contest 013&014

Atcoder 241

AtCoder Beginner Contest 243

标签