RooksPlacement | Topcoder Archive

Problem Statement

You will be given three integers N, M and K. You are to calculate the number of ways to place K rooks on a NxM chessboard in such a way that no rook is attacked by more than one other rook. A rook is attacked by another rook if they share a row or a column and there are no other rooks between them. To avoid problems with big numbers the calculation should be done modulo 1,000,001.

Definition

Class:: RooksPlacement
Method:: countPlacements
Parameters:: int, int, int
Returns:: int
Method signature:: int countPlacements(int N, int M, int K)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
M will be between 1 and 50, inclusive.
K will be between 1 and 100, inclusive.

Examples

```
4
```
```
5
```
```
2
```
```
Returns: 190
```
There are only two rooks and therefore all placements are valid. The number of placements is (4 * 5) * (4 * 5 - 1) / 2 = 190.
```
2
```
```
3
```
```
3
```
```
Returns: 6
```
There are 6 possible placements: XX. X.X .XX ..X .X. X.. ..X .X. X.. XX. X.X .XX
```
6
```
```
7
```
```
20
```
```
Returns: 0
```
```
23
```
```
37
```
```
39
```
```
Returns: 288688
```

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.