BearFills | Topcoder Archive

Problem Statement

Bear Limak has a rectangular grid that consist of H times W unit square cells. Limak also has N square stamps. The lengths of the stamps' sides are 2^0, 2^1, ..., 2^(N-1).

A set of stamps is called good if it can be used to cover the entire grid. Each stamp must be placed along the grid lines. I.e., for each stamp each cell is either completely covered by the stamp or not covered at all. The stamps may overlap arbitrarily. The stamps may also cover areas outside of the grid. For example, you may use a 4x4 stamp just to cover a single cell in the corner of the grid.

You are given the int N and the longs H and W. Limak wants to choose a subset of his stamps that will be good. Return the number of ways in which he can do so.

Definition

Class:: BearFills
Method:: countSets
Parameters:: int, long, long
Returns:: long
Method signature:: long countSets(int N, long W, long H)
(be sure your method is public)

Notes

N will be between 1 and 60, inclusive.
H and W will be between 1 and 10^18, inclusive.

Constraints

Examples

```
3
```
```
1
```
```
3
```
```
Returns: 5
```
He has a 1x3 rectangle and 3 square stamps. The stamps' sides are 1, 2, and 4. The good sets of stamps are the following ones: (1,2), (1,2,4), (1,4), (2,4), and (4).
```
3
```
```
3
```
```
5
```
```
Returns: 1
```
He has a 3x5 rectangle and 3 square stamps. The stamps' sides are 1, 2, and 4. He needs all of them.
```
60
```
```
3
```
```
2
```
```
Returns: 1152921504606846972
```
He has a 3x2 rectangle and 60 square stamps. Only four sets are not good: (), (1), (2), and (1,2). The answer is 2^60-4.
```
6
```
```
5
```
```
4
```
```
Returns: 56
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.