专栏文章

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

FFJ_EYoungOneC
B4105题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqmsqh7
此快照首次捕获于
2025/12/04 07:21
3 个月前
此快照最后确认于
2025/12/04 07:21
3 个月前
查看原文

原题链接

P8649 [蓝桥杯 2017 省 B] k 倍区间
B4105 [CSP-X2024 山东] 消灭怪兽

解题思路

20pts

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

40pts

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

100pts

我们用 sis_i 表示 a1+a2+…aia_1+a_2+\dots a_i 的和，假设有 al+al+1+⋯+ara_l + a_{l+1} + \dots + a_r 为 kk 的倍数，即 sr≡sl−1(modb)s_r \equiv s_{l-1} \pmod b。
所以我们要计算以 rr 左右区间右端点时的方案数，仅需统计 i∈[1,r−1]i \in [1, r - 1] 中与 srs_r 同余的 sis_i 的数量即可。
时间复杂度 O(n)O(n)。

AC_Code

CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...