TopCoder problem "RooksPlacement" used in SRM 354 (Division I Level Three)



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

0)
    
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.
1)
    
2
3
3
Returns: 6

There are 6 possible placements:

XX.    X.X    .XX
..X    .X.    X..

..X    .X.    X..
XX.    X.X    .XX
2)
    
6
7
20
Returns: 0
3)
    
23
37
39
Returns: 288688

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7658

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10711&pm=7658

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming