A. 优美子数列
题目描述
数学家小 \(Q\) 得到了一个长度为 \(n\) 的数列 {\(a_n\)}。
小 \(Q\) 的幸运数字是 \(k\)，所以他认为，若一个子数列 \(a_l\), \(a_l + 1\), …, \(a_r\) 的和为 \(k\) 的倍数，则该子数列是优美子数列。
小 \(Q\) 现在想考考你，{\(a_n\)} 里有多少个优美子数列呢？
输入格式
第一行输入两个正整数 \(n,k\)。
接下来一行输入 \(n\) 个数，代表 \(a_1\) 到 \(a_n\)。
输出格式
输出一行一个正整数，表示优美子数列的个数。
样例输入
5 3
1 2 3 4 5
样例输出
7
数据规模
对于 \(60\%\) 的数据，\(n \le 1000\)；
对于 \(100\%\) 的数据，\(1 \le n \le 2 \times 10^5\)，\(1 \le k \le 10^7\)，\(-10^9 \le a_i \le 10^9\)。
点击查看代码
#include<iostream>
#include<map>
using namespace std;
long long n, k, a[200005];
long long ans = 0;
map<long long, long long> mp;
int main() {
cin >> n >> k;
mp[0] ++;
for(int i = 1; i <= n; i ++) {
int x;
cin >> x;
x %= k;
a[i] = ((a[i - 1] + x) % k + k) % k; // 防止负数
ans += mp[a[i]];
mp[a[i]] ++;
}
cout << ans << endl;
return 0;
}
编译结果
compiled successfully
time: 309ms, memory: 11632kb, score: 100, status: Accepted
> test 1: time: 0ms, memory: 3492kb, points: 10, status: Accepted
> test 2: time: 0ms, memory: 3384kb, points: 10, status: Accepted
> test 3: time: 1ms, memory: 3408kb, points: 10, status: Accepted
> test 4: time: 0ms, memory: 3360kb, points: 10, status: Accepted
> test 5: time: 1ms, memory: 3376kb, points: 10, status: Accepted
> test 6: time: 0ms, memory: 3464kb, points: 10, status: Accepted
> test 7: time: 14ms, memory: 4752kb, points: 10, status: Accepted
> test 8: time: 174ms, memory: 11632kb, points: 10, status: Accepted
> test 9: time: 49ms, memory: 7076kb, points: 10, status: Accepted
> test 10: time: 70ms, memory: 4912kb, points: 10, status: Accepted