这题恶心了我好几天

一直不不懂啥意思

他娘的

注意
一维前缀和的赋值 cin >> s[i];s[i] += s[i -1]
右端点i固定，枚举从第1位开始到第i-1位的区间 和是K的倍数
* 前i-1个前缀和s[0…i-1] 中有多少 % k 的余数 等于 s[当前i] % k的余数 用数组来存放余数的个数

s[i] - s[0] % k == 0;
s[i] - s[1] % k == 0;
s[i] - s[2] % k == 0;
     ......
s[i] - s[i - 1] % k == 0;

//说明 s[i] % k 的余数 等于 s[0]...s[i -1] % k的余数    计算有多少个即可

代码

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;
LL s[N], cnt[N];

int main()
{
    int n, k;
    cin >> n >> k;

    //前缀和
    for(int i = 1; i <= n; i ++)
    {   
        cin >> s[i];
        s[i] += s[i - 1];
    }

    LL res = 0;
    cnt[0] ++; // s[0] % k = 0  所以余数为0的个数加1；
    for(int i = 1; i <= n; i++)
    {
        res += cnt[s[i] % k];
        //前i-1个前缀和s[0...i-1] 中有多少 % k 的余数 等于 s[当前i] % k的余数
        cnt[s[i] % k] ++;
        //不包括当前的s[i]，当前的s[i] % k 的余数 进入到下一个i的计算 
    }

    cout << res << endl;
    return 0;
}