PlankTiling | Topcoder Archive

Problem Statement

You have a sufficient supply of identical planks. Each plank has the shape of an 1 times H rectangle.

The floor of your room is also a rectangle. Its width is W and its height is 2H-1. You want to use the planks you have to tile the floor. The entire floor must be covered and the planks must not overlap. (The width W is guaranteed to be a multiple of H, so this is always possible.)

You are given the two ints H and W. Return the number of ways to tile the floor, modulo 1,000,000,007.

Definition

Class:: PlankTiling
Method:: sumup
Parameters:: int, int
Returns:: int
Method signature:: int sumup(int H, int W)
(be sure your method is public)

Constraints

H will be between 2 and 1000, inclusive.
W will be between 2 and 1000, inclusive.
W will be a multiple of H.

Examples

```
2
```
```
4
```
```
Returns: 11
```
We are using 1x2 planks to tile a rectangle of width 4 and height 3. There are eleven different ways to do so:
```
4
```
```
4
```
```
Returns: 5
```
```
3
```
```
9
```
```
Returns: 121
```
```
29
```
```
841
```
```
Returns: 193514715
```

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.