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].
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
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:
@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.
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.
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!
@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