读完题看完数据范围n^2必然要TLE,但是我一开始还是硬着头皮去写了.(穷举左右边界)因为我不知道如何优化
直到看完一些大佬的题解,豁然开朗.
一些解释:
prefix[i]表示区间[1,i]的前缀和 % k;
对于某一位置i,如果存在j < i使得(sum[i] - sum[j]) % k == 0,也即sum[i] % k == sum[j] % k;
线性扫描,使用cnt数组存储前缀和 % k相同的位置的个数.
最令人头疼的是为什么要初始化cnt[0] = 1呢,因为假设A1,A2…Ai的和模k恰好等于0,该区间不需要减去前面某一段的和
所以,我们是假设了在prefix[0]时存在左边界0的.

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1e5 + 5;
int n,k;
long long prefix[N],cnt[N];
int main () {
    cin >> n >> k;
    long long ans = 0,t;
    cnt[0] = 1;
    for (int i = 1;i <= n;i++)  {
        cin >> t;
        prefix[i] = (prefix[i - 1] + t) % k;
        ans += cnt[prefix[i]];
        cnt[prefix[i]]++;
    }
    cout << ans << endl;
    return 0;
}