### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Shiplu Hawlader and Mahbubul Hasan

**Editorialist:** Lalit Kundu

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Dynamic Programming

Precomputation

### PROBLEM:

Given N numbers, and a number M, we need to find number of subsets such that sum of elements of subset is divisible by M.

1 <= N <= 100000

1 <= M <= 100

At most 3 test cases with 30 queries in each test. That is 90 queries at most.

### EXPLANATION:

If you are not familiar with dynamic programming, read topcoder tutorial here first.

So, here we define a state DP[i][j] which stores the number of ways to choose subsets from A_{0}…A_{i} such that subset sum modulo M is j.

Now,

```
DP[i][j]= DP[i-1][j] + // we don't choose the i'th element
DP[i-1][(j-A[i])%M] // we choose the i'th element
```

Our answer will be DP[N-1][0]. But here, complexity will be N*M for each query, which will time out.

The advantage here we have is that M<=100. A[i] doesn’t matter to us. What matters is what A[i]%M is. So,

```
for i=0 to M-1:
count[i]=number of A[j] such that A[j]%m=i
```

The above array count, can be calculated using hashing.

Again, we have to use dynamic programming.

We define a new state DP[i][j] which stores, the number of subsets which consists of only those A_{j}’s whose modulo M is less than or equal to i, and subset sum modulo M is j.

choose(n,r) is number of ways to choose r elements out of n distinct elements ie. (n!)/((r!)*(n-r)!)

Now,

```
DP[i][j] =
DP[i-1][(j-i*0)%M]*choose(count[i],0)+// we don't pick any one of the count[i] choices we have.
DP[i-1][(j-i*1)%M]*choose(count[i],1)+// we can pick any one of the count[i] choices we have.
DP[i-1][(j-i*2)%M]*choose(count[i],2)+// we can pick any two of the count[i] choices we have.
.
.
.
DP[i-1][(j-i*count[i])%M]*choose(count[i],count[i])// we pick all of the count[i] choices we have
```

But, the complexity here will still remain N*M. We can rewrite the above as:

```
DP[i][j] =
DP[i-1][(j-0)%M]*summation[k=0 to count[i], where (k*i)%M==0]{choose(count[i],k)} +
DP[i-1][(j-1)%M]*summation[k=0 to count[i], where (k*i)%M==1]{choose(count[i],k)} +
.
.
.
DP[i-1][(j-(M-1))%M]*summation[k=0 to count[i], where (k*i)%M==(M-1)]{choose(count[i],k)}
```

We can precompute all the summation terms above for each query in O(N).

So, complexity will be O(M*M*M) for each query.

### AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon.