Soluție HackerRank pentru Consecutive Subsequences, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod…
- Problemă: Consecutive Subsequences
- Domeniu: Combinatorics
- Limbaj: C++14
Challenge: Consecutive Subsequences
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 50.0 / 50
Submission status: Accepted
Submission score: 1.0
Submission ID: 464734580
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/consecutive-subsequences/problem
Cerință
Jigar got a sequence of __n__ positive integers as his birthday present! He likes consecutive subsequences whose sum is divisible by __k__. He asks you to write a program to count them for him.
__Input Format__
The first line contains T, the number of testcases.
__T__ testcases follow. Each testcase consists of 2 lines.
The first line contains n and k separated by a single space.
And the second line contains __n__ space separated integers.
__Output Format__
For each test case, output the number of consecutive subsequenences whose sum is divisible by __k__ in a newline.
__Constraints__
1 ≤ T ≤ 20
1 ≤ n ≤ 10<sup>6</sup>
1 ≤ k ≤ 100
1 ≤ a[i] ≤ 10<sup>4</sup>
__Sample Input__
<pre>
2
5 3
1 2 3 4 1
6 2
1 2 1 2 1 2
</pre>
__Sample Output__
<pre>
4
9
</pre>
__Explanation__
For
1 2 3 4 1
there exists, 4 subsequences whose sum is divisible by 3, they are
3
1 2
1 2 3
2 3 4
For
1 2 1 2 1 2
there exists, 9 subsequences whose sum is divisible by 2, they are
2
2
2
1 2 1
1 2 1
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1 2
Cod sursă
//consecutive-subsequences.cpp
//Consecutive Subsequences
//Weekly Challenges - Week 6
//Author: derekhh
#include<iostream>
#include<cstring>
using namespace std;
int cnt[100];
int main()
{
int t;
cin >> t;
while (t--)
{
memset(cnt, 0, sizeof(cnt));
int n, k, num, sum = 0;
cin >> n >> k;
cnt[0] = 1;
for (int i = 0; i < n; i++)
{
cin >> num;
sum += num;
if (sum >= k) sum %= k;
cnt[sum]++;
}
long long ret = 0;
for (int i = 0; i < k; i++)
ret += (long long)cnt[i] * (cnt[i] - 1) / 2;
cout << ret << endl;
}
return 0;
}