CSP-X2024山东小学组T2：消灭怪兽

题目链接

题目名称

题目描述

怪兽入侵了地球！

为了抵抗入侵，人类设计出了按顺序排列好的 $n$ 件武器，其中第 $i$ 件武器的攻击力为$a_i$，可以造成 $a_i$ 的伤害。

武器已经排列好了，因此不能改变顺序。某件武器可以单独攻击，也可以与相邻的武器进行组合攻击。

具体来说，每次你可以把相邻的若干个（可以为 $1$ 个，即不进行组合）连续
的武器组合起来进行攻击，则攻击力为这些连续的武器攻击力之和。

来自外星的怪兽拥有无敌护盾，不会受到任何伤害。但是人类在交战过程中发现怪兽有个致命的弱点：每次当受到 $k$ 或 $k$ 的倍数的伤害时，怪兽的无敌护盾就能被打破。

请你帮助人类求出有多少种组合武器的方案，使得造成的伤害能打破怪兽的无敌护盾。

输入格式

第一行两个正整数 $n,k$ 如题所述； 第二行为 $n$ 个正整数，其中第 $i$ 个数 $a_i$ 表示第 $i$ 件武器的攻击力。

输出格式

一行一个整数表示答案。

样例

样例输入 #1

5 3
1 2 3 4 5

样例输出 #1

7

样例输入 #2

10 11
1 4 8 10 16 19 21 25 30 43

样例输出 #2

7

样例输入 #3

6 2
2 2 2 2 2 2

样例输出 #3

21

提示

【样例1解释】
$k=3$，而区间 [1, 2]，[1, 3]，[1, 5]，[2, 4]，[3, 3]，[3, 5]，[4, 5] 的区间
和均为 $3$ 或 $3$ 的倍数，故一共有 $7$ 种方案。

【数据范围】

• 20% 的数据，$n,k\le 100$；
• 40% 的数据，$n,k\le 10000,1\le a_i\le k$；
• 另外存在10% 的数据，$k=2$；
• 另外存在10% 的数据，所有的 $a_i$ 均相等。
• 100% 的数据，$1\le n\le 10^6$ , $2\le k\le 10^6$ , $1\le a_i\le 10^9$。

算法思想

朴素版前缀和

根据题目描述，只需要预处理出前缀和，然后枚举区间的开始位置$L$和结束位置$R$，判断$S[R]-S[L-1]$是否为$k$的倍数就可以了。

时间复杂度

• 处理前缀和的时间复杂度为$O(n)$
• 枚举开始和结束位置的时间复杂度为$O(n^2)$

总的时间复杂度为$O(n^2)$，其中$1\le n\le 10^6$，可以拿到60分。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
LL a[N], s[N];
int main()
{
    int n, k;
    cin >> n >> k;
    LL ans = 0;
    for(int i = 1; i <= n; i ++) 
    { 
        cin >> a[i]; 
        s[i] = s[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= i; j ++)
        {
            LL x = s[i] - s[j - 1];
            if(x % k == 0) ans ++;
        }
    }
    cout << ans << endl;
}

算法优化

连续区间$[L,R]$中所有数的和是$11$的倍数，那么前缀和数组中$S[R]-S[L-1]$一定是$11$的倍数，也就是说$(S[R]-S[L-1])mod11=0$。根据这个性质，不妨将前缀和数组中的每个值$mod11$，得到一个余数数组，如下图所示。

如果存在两个位置$x$和$y$余数相同，它们相减的差为$0$，那么说明序列中区间$[x+1,y]$中所有数的和为$11$的倍数。

这样，只需要统计一下，余数数组中值为$i$的个数，不妨设有$cnt$个，那么任意两个都可以构成一个区间，其中所有数为$11$的倍数，那么对答案的贡献为：$cnt\times (cnt-1)/2$。

时间复杂度

• 处理前缀和的时间复杂度为$O(n)$
• 遍历所有余数的时间复杂度为$O(k)$

总的时间复杂度为$O(n+k)$，其中$1\le n\le 10^6$ , $2\le k\le 10^6$ 。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
int a[N], s[N], cnt[N];
int main()
{
    
    int n, k;
    cin >> n >> k;
    cnt[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        s[i] = (s[i - 1] + a[i]) % k;
        cnt[s[i]] ++;
    }
    
    LL ans = 0;
    for(int i = 0; i < k; i ++)
    {
        if(cnt[i] > 1) ans += (LL) cnt[i] * (cnt[i] - 1) / 2; 
    }
    cout << ans << endl;
}