题解：B4105 [CSP-X2024 山东] 消灭怪兽

· · 题解

原题链接

P8649 [蓝桥杯 2017 省 B] k 倍区间

B4105 [CSP-X2024 山东] 消灭怪兽

解题思路

20pts

我们可以枚举区间左端点 l 和区间右端点 r，再循环统计 [l, r] 的和并是否是 k 的倍数，时间复杂度 O(n^3)。

40pts

我们可以使用前缀和算法优化上述统计 [l, r] 的区间和，时间复杂度 O(n^2)。

100pts

我们用 s_i 表示 a_1+a_2+\dots a_i 的和，假设有 a_l + a_{l+1} + \dots + a_r 为 k 的倍数，即 s_r \equiv s_{l-1} \pmod b。

所以我们要计算以 r 左右区间右端点时的方案数，仅需统计 i \in [1, r - 1] 中与 s_r 同余的 s_i 的数量即可。

时间复杂度 O(n)。

AC_Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n, k;
int h[N];

int main()
{
    cin >> n >> k;
    h[0] ++;
    LL s = 0, res = 0;
    for (int i = 1; i <= n; ++ i )
    {
        int x;
        cin >> x;
        s += x;
        res += h[s % k] ++;
    }

    cout << res << endl;

    return 0;
}