# UVa 10616

Jump to navigation
Jump to search

## Contents

## 10616 - Divisible Group Sums[edit]

## Summary[edit]

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

## Explanation[edit]

We can use memoization to solve this problem. Let be the input numbers, and let 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 , or we can pass on item i, leaving us at state . The total number of subsets at state i, j, k is simply the sum of the of counts at each branch.

## Gotchas[edit]

- 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.

## Implementations[edit]

## Input[edit]

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[edit]

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