@migos.
In magic set problem, you have to select the good sequences (but actually it is sub sequences)
X_1, X_2, \cdots X_N
such that sum of each and every individual subseqences, let say the subsequences of
X_1 are X_{1a}, X_{1b} \cdots and so on
obtained by the good sequences, are divisible by m.
I know it is sounding a bit confusing but let me clear it up
first I am considering the sample input output itself
$
2,3\
1, 2\
$
if you are thinking that if we take consider the good sequence (which is a wrong idea)
\{1,2\} cause 1+2 = 3 is divisible by 3, wait and think. We have to see the sum of all subsequences individually
\{1,2\} has subsequences (ignoring empty) as
\{1\} Sum = 1 which is not divisible by 3
\{2\} Sum = 2 which is not divisible by 3
\{1,2\} Sum = 3 which is divisible by 3
We could have taken last one, but the all the subseqences of {1,2} didn’t satisfy the given conditions. So there are 0 good sequence
Now in 2^{nd} i/p
$
2,3\
1,3
$
We can consider a good sequence as \{3\}
Since all susequences of \{3\} = \{3\} Sum is divisible by 3. So the answer is 1
One thing you notice you can only form good sequence which each element divisible by m or every element of good sequence must be a multiple of m as their sum has to be divisible by m. You can easily prove it if not then ask.
Now taking a another example
$
7,3\
3, 6, 9, 10, 11, 12, 13
$
So you have to select every sequences in which each and every element is a multiple of m which is 3
How many sequences can be there
\{3\}, \{6\}, \{9\}, \{12\}, \{3,6\}, \{3,9\}, \{3,12\}, \cdots and so on. You can see the pattern here.
Or the the simpler way is to make the largest subsequence possible which is \{3,6,9,12\} and count all its non empty subsequences as it will include all possible subsequences and which is the answer.
Or 2^{Size\,of\,Largest\,Subsequence} - 1 = 2^4 - 1 = 15
I hope you get it. See code https://www.codechef.com/viewsolution/19117599
