题目链接

1230. K倍区间 - AcWing题库

一些话

相似题型：隐藏的牛

NYIST(计科ACM&TC)第三次招新赛_栞那Kanna的博客-CSDN博客

切入点

如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j]是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

求有多少个类问题，符合枚举的特征

求区间和问题，符合前缀和特征

流程

1.看数据范围

数据范围

1≤N,K≤100000；

1≤Ai≤100000

n = 1e6,就算是区间枚举也会超时，O((n+1)*(n/2))

所以只能单重循环枚举

2.读题寻找条件

题目要求 区间和%k==0

即(s[i] - s[j-1] ) % k == 0

这需要双循环枚举两个点

此时开始想能不能把点拆开来，枚举一个就得到另一个

拆分公式

((s[i] % k) - (s[j-1] % k ) + k) % k == 0（这是一般的减法取余）

因为i与j-1的组合等价于j-1与i的组合，所以这两个值可以互相调换成差值大于0

的情况，此时就可以直接写成s[i] % k == s[j-1] % k;

枚举的时候只要s[i]%k的结果相同，就可以组成一个符合要求的区间。

所以就用类似牛腿问题的计数方法

ans += cnt[s[i]%k];

cnt[s[i]%k]++;

此外如果s[i] 自身%k== 0也要计数

cnt[s[i]%k] = 1,就可以让这种情况每次计入ans时比其他情况多1

套路

求情况数量题

一个数组、字符串内的元素是特殊的某种情况，组合可以形成满足题意的情况：

元素可以任意两两组合：

用一重循环

cnt统计当前特殊情况元素数量

if（特殊情况出现）{

       res += cnt;，

       cnt++；

}

这是用前面出现的特殊情况元素和当前新出现的一个特殊情况元素组合，从而新组合成cnt种满足题意的情况

ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int cnt[N];
long long f[N];
int main(){
    int n,k;
    cin >> n >> k;
    for(int i = 1;i <= n;i++) {
        scanf("%lld",&f[i]);
        f[i] += f[i-1];
    }
    cnt[0] = 1;
    long long ans = 0;
    for(int i = 1;i <=n;i++){
        ans += cnt[f[i]%k];
        cnt[f[i]%k]++;
    }
    cout << ans << endl;
    return 0;
}