【题解】P8649 题解

· · 题解

P8649 题解

思路分析

一道简单前缀和的题。

首先，看到”连续子序列求和”这一要求时，我们果断选择前缀和解答。

接着我们要分析，什么时候这段区间的和为 K 的倍数？显然，当区间和 \text{sum} 满足 K \mid \text{sum}，即 \text{sum} \bmod k = 0 时，为 K 的倍数。

而又由于原数组 a 中 a_l \sim a_{r} 的区间和 \text{sum} 等于 p_r - p_{l-1}（p 为 a 的前缀和数组），所以 p_r - p_{l-1} \equiv 0 \pmod k。所以 p_r \equiv p_{l-1} \pmod k。

也就是说，我们只需判断前缀和模 k 是否同余就可以了，但一个个枚举区间有点慢，怎么办呢？

我们可以来一个“回手掏”，从”模 k 同余“入手。我们可以开一个 map 记录每个前缀和模 k 的余数出现的次数，然后在同余数的情况下，任选两个前缀和，必然能够构成一段区间，这段区间的和为 K 的倍数。设某个余数出现了 x 次，则必会存在 \text{C}^{2}_{x} 段区间和为 k 的倍数。

注意：map 要将余数 0 出现的次数初始化为 1。这样的话，如果 0 出现了 x 次的话，则必会存在 \text{C}^2_{x + 1} 段区间和为 k 的倍数。为什么呢？因为，根据题意，一个数也算一段区间，即答案为：

C^2_{x} + x = \dfrac{x(x-1)}{2} + x = \dfrac{x(x-1)}{2} + \dfrac{2x}{2} = \dfrac{x(x-1 + 2)}{2} = \dfrac{x(x+1)}{2} = \text{C}^2_{x+1}

依据上述步骤实现即可，然后记得开 long long。

代码

#include <iostream>
#include <map>
#define int long long
using namespace std;

map <int, int> mp; //记录每个余数出现个数的数组

signed main()
{
    int n, k, ans = 0;
    cin >> n >> k;
    mp[0] = 1; //初始化 0 出现的次数为 1
    for(int i = 1;i <= n;i++)
    {
        int x;
        cin >> x;
        ans += (x % k); //计算前缀和
        mp[ans % k]++; //前缀和模 k
        ans %= k;
    }
    int cnt = 0;
    for(int i = 0;i < k;i++) cnt += (mp[i] * (mp[i] - 1)) / 2; //根据上述公式计算答案
    cout << cnt << endl;
    return 0;
}