@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