competitive..
Pages: 12
Please explain the below question with more testcases and explaining each of them.
Katya has a sequence of integers a1,a2,…,an and an integer m.
She defines a good sequence of integers as a non-empty sequence such that the sums of all its non-empty subsequences are divisible by m.
Katya wants to know the number of good subsequences of the sequence a. Can you help her?
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers n and m.
The second line contains n space-separated integers a1,a2,…,an.
Output
For each test case, print a single line containing one integer — the number of good subsequences.
Constraints
1≤T≤1,000
1≤n≤30
1≤m≤1,000
1≤ai≤1,000 for each valid i
Subtasks
Subtask #1 (30 points): 1≤n≤5
Subtask #2 (70 points): original constraints
Example Input
2
2 3
1 2
2 3
1 3
Example Output
0
1
Explanation
Example case 1: There are no good subsequences.
Example case 2: There is exactly one good subsequence of a: [3].
Katya has a sequence of integers a1,a2,…,an and an integer m.
She defines a good sequence of integers as a non-empty sequence such that the sums of all its non-empty subsequences are divisible by m.
Katya wants to know the number of good subsequences of the sequence a. Can you help her?
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers n and m.
The second line contains n space-separated integers a1,a2,…,an.
Output
For each test case, print a single line containing one integer — the number of good subsequences.
Constraints
1≤T≤1,000
1≤n≤30
1≤m≤1,000
1≤ai≤1,000 for each valid i
Subtasks
Subtask #1 (30 points): 1≤n≤5
Subtask #2 (70 points): original constraints
Example Input
2
2 3
1 2
2 3
1 3
Example Output
0
1
Explanation
Example case 1: There are no good subsequences.
Example case 2: There is exactly one good subsequence of a: [3].
EDIT: I tested this idea (and another similar idea) and got "wrong answer", so I obviously don't understand the question. <end edit>
If every non-empty subsequence of a "good sequence" must be divisible by m, then obviously every individual number in the subsequence must be divisible by m. So you just need to determine the lengths the longest subsequences of numbers divisible by m and calculate how many non-empty subsequences they contain. If the length is len, then the number of non-empty subsequences is len * (len + 1) / 2 (i.e., the sum of values 1 to len, because there is 1 subsequence of length len, 2 of length len-1, 3 of length len-2, etc.).
Suppose the input is
Then the longest subsequences of numbers divisible by 2 are:
That's a total of 1 + 3 + 6 == 10 "good sequences"
If every non-empty subsequence of a "good sequence" must be divisible by m, then obviously every individual number in the subsequence must be divisible by m. So you just need to determine the lengths the longest subsequences of numbers divisible by m and calculate how many non-empty subsequences they contain. If the length is len, then the number of non-empty subsequences is len * (len + 1) / 2 (i.e., the sum of values 1 to len, because there is 1 subsequence of length len, 2 of length len-1, 3 of length len-2, etc.).
Suppose the input is
1 // 1 test case 11 2 // 11 numbers; check for divisibility by 2 4 1 3 2 6 7 8 6 4 1 5 |
Then the longest subsequences of numbers divisible by 2 are:
4 length: 1 1 * (1 + 1) / 2 == 1 2 6 length: 2 2 * (2 + 1) / 2 == 3 8 6 4 length: 3 3 * (3 + 1) / 2 == 6 |
That's a total of 1 + 3 + 6 == 10 "good sequences"
Last edited on
i didnt get that exactly. why every individual number should be divisible by m, we need to check for sum?
I can't understand what you're asking.
And I already said that my answer is wrong, anyway.
And I already said that my answer is wrong, anyway.
@tpb i think, the number of non-empty subsequences should be calculated as the sum of
pow(2,len)-1 for all the possible subsequences. Although, i haven't understood the question as well.
Ok, I have understood the question.
we have to find the good subsequences which satisfy the condition given in the question, and for that we need to find those subsequences of the given sequence that contain only those numbers which are divisible by
For example,
The numbers we are interested in this sequence are
EDIT: If you don't know correctly what a subsequence is, then visit https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/
we have to find the good subsequences which satisfy the condition given in the question, and for that we need to find those subsequences of the given sequence that contain only those numbers which are divisible by
m in this case.For example,
1 7 3 1 3 6 4 5 9 2 |
The numbers we are interested in this sequence are
3,6 and 9. Now the no. of subsequences that can be formed by these numbers equals pow(2,3)-1 as there are 3 numbers. In general, if there are n numbers divisible by m in the sequence then answer would be pow(2,n)-1.EDIT: If you don't know correctly what a subsequence is, then visit https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/
Last edited on
You should try dp solution.
Let s denote the input sequence with length N, and K be the given divisor.
dp[i][j] = the number of subsequences of the sequence s[0..i] with remainder equal to j. We will compute dp for all 0 <= i < N and 0 <= j < K.
dp[i][j] = 0 for all (i, j)
dp[0][s[0] mod K] += 1
for i = 1 .. N - 1
for j = 0 .. K - 1
dp[i][j] = dp[i - 1][j]
for j = 0 .. K - 1
dp[i][(j + s[i]) mod K] += dp[i - 1][j]
The result is dp[N - 1][0]
Try this logic. Keep coding!
Let s denote the input sequence with length N, and K be the given divisor.
dp[i][j] = the number of subsequences of the sequence s[0..i] with remainder equal to j. We will compute dp for all 0 <= i < N and 0 <= j < K.
dp[i][j] = 0 for all (i, j)
dp[0][s[0] mod K] += 1
for i = 1 .. N - 1
for j = 0 .. K - 1
dp[i][j] = dp[i - 1][j]
for j = 0 .. K - 1
dp[i][(j + s[i]) mod K] += dp[i - 1][j]
The result is dp[N - 1][0]
Try this logic. Keep coding!
@helpinghand
After trying your approach still i am able to pass only subtask 1 only, for subtask 2 it is showing WA.
Can you tell why it is like that??
After trying your approach still i am able to pass only subtask 1 only, for subtask 2 it is showing WA.
Can you tell why it is like that??
Last edited on
@helping hand what about (4,5) subsequence it is also a good subsequence because its further subsequences being (4) and (5) and sum of them is divisible by 3
@quirkly1234 your logic will fail in the sample input 2 itself,it will give 0 instead of 1 as a answer.
and the code you mentioned is on stackoverflow in which the the man who had written the answer is also saying at the end that there is error in his dp initialization.
So your logic will not work.
Check the comments in post: https://stackoverflow.com/questions/32777252/count-total-subsequences-whose-sum-is-divisible-by-k
and the code you mentioned is on stackoverflow in which the the man who had written the answer is also saying at the end that there is error in his dp initialization.
So your logic will not work.
Check the comments in post: https://stackoverflow.com/questions/32777252/count-total-subsequences-whose-sum-is-divisible-by-k
Last edited on
@helpinghand could you explain your logic please and once explain me the question again please its a request
i am done with both but magicset i solved it by chance, so i just wanted the explanation of magicset
Last edited on
@helpinghand gave me wrong answer for long long as well so printed unsigned long long
@arj0001 you should definitely first understand what a subsequence exactly is.
visit here: https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/
visit here: https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/
@hackr is it giving correct answer for both test cases for unsigned long long int?
Pages: 12