给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入格式 第一行包含两个整数N和K。(1 <= N, K <= 100000) 以下N行每行包含一个整数Ai。(1 <= Ai <= 100000) 输出格式 输出一个整数,代表K倍区间的数目。
时间: 2024-02-13 19:00:05 浏览: 260
k倍区间 蓝桥(技巧)
以下是C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000
int N, K;
int A[MAXN + 1];
int S[MAXN + 1];
long long cnt[MAXN + 1];
struct node {
int key;
int value;
struct node *next;
};
struct hashtable {
int size;
struct node **table;
};
struct node *node_new(int key, int value) {
struct node *p = (struct node *)malloc(sizeof(struct node));
p->key = key;
p->value = value;
p->next = NULL;
return p;
}
struct hashtable *hash_new(int size) {
struct hashtable *h = (struct hashtable *)malloc(sizeof(struct hashtable));
h->size = size;
h->table = (struct node **)calloc(size, sizeof(struct node *));
return h;
}
void hash_put(struct hashtable *h, int key, int value) {
int index = (key % h->size + h->size) % h->size;
struct node *p = h->table[index];
while (p != NULL) {
if (p->key == key) {
p->value += value;
return;
}
p = p->next;
}
struct node *new_node = node_new(key, value);
new_node->next = h->table[index];
h->table[index] = new_node;
}
int hash_get(struct hashtable *h, int key) {
int index = (key % h->size + h->size) % h->size;
struct node *p = h->table[index];
while (p != NULL) {
if (p->key == key) {
return p->value;
}
p = p->next;
}
return 0;
}
int main() {
scanf("%d%d", &N, &K);
for (int i = 1; i <= N; i++) {
scanf("%d", &A[i]);
S[i] = (S[i - 1] + A[i]) % K;
}
struct hashtable *h = hash_new(K);
for (int i = 0; i < K; i++) {
cnt[i] = 0;
}
cnt[0] = 1;
for (int i = 1; i <= N; i++) {
cnt[S[i]] += hash_get(h, S[i]);
hash_put(h, S[i], 1);
}
long long ans = 0;
for (int i = 0; i < K; i++) {
ans += cnt[i] * (cnt[i] - 1) / 2;
}
printf("%lld\n", ans);
return 0;
}
```
其中,node是哈希表中存储的节点,包含键值对和指向下一个节点的指针。hashtable是哈希表结构体,包含哈希表的大小和指向桶数组的指针。hash_new函数用于创建一个新的哈希表,hash_put函数用于在哈希表中插入一个键值对,hash_get函数用于获取指定键的值。在主函数中,我们先读入数列,并计算前缀和数组S。然后,我们使用哈希表来记录余数出现的次数,并根据公式计算答案。最后,输出答案即可。
阅读全文