# UVa 10616

## Summary

Count how many fixed size subset sums are divisible by a given divisor.

## Explanation

We can use memoization to solve this problem. Let ${\displaystyle a_{1},a_{2},...a_{n}}$ be the input numbers, and let ${\displaystyle d}$ be the desired divisor. The state space is current index, current sum mod d, numbers left to pick. When at index i, with mod j, and k numbers left to select, we can either take the item at index i, leaving us with at state ${\displaystyle i+1,(j+a[i])\%d,k-1}$, or we can pass on item i, leaving us at state ${\displaystyle i+1,j,k}$. The total number of subsets at state i, j, k is simply the sum of the of counts at each branch.

## Gotchas

• The input is a signed integer, negative numbers will appear in the input.
• The modulo (%) operator may not work as intended for negative numbers in your favorite langauge, try it.

```10 2
1
2
3
4
5
6
7
8
9
10
5 1
5 2
5 1
2
3
4
5
6
6 2
3 1
1 -1
3 2
0 0

```

## Output

```SET 1:
QUERY 1: 2
QUERY 2: 9
SET 2:
QUERY 1: 1
SET 3:
QUERY 1: 1
SET 4:
QUERY 1: 1
```