ShrooksOnTheBoard | Topcoder Archive

Problem Statement

A K-shrook is a fairy chess piece that can move horizontally in both directions for at most K squares. Here is an illustration of 2-shrook possible moves:

Two K-shrooks attack each other if one of them can reach the other shrook's square in one move. You are given a board with H rows and W columns. Find out the number of ways to place an arbitrary positive amount of K-shrooks on this board so that no two of them attack each other. Return this number modulo 100003.

Definition

Class:: ShrooksOnTheBoard
Method:: count
Parameters:: int, int, int
Returns:: int
Method signature:: int count(int K, int H, int W)
(be sure your method is public)

Constraints

K will be between 1 and 1,000,000,000, inclusive.
H will be between 1 and 1,000,000,000, inclusive.
W will be between 1 and 1,000,000,000, inclusive.

Examples

```
1
```
```
1
```
```
3
```
```
Returns: 4
```
The possible placements are "S..", ".S.", "..S" and "S.S".
```
1
```
```
2
```
```
2
```
```
Returns: 8
```
There can not be more than 1 shrook in a row.
```
3
```
```
4
```
```
9
```
```
Returns: 56963
```

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.