TopCoder problem "ShrooksOnTheBoard" used in TCO10 Wildcard (Division I Level Three)



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

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

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14286&pm=11072

Writer:

dkorduban

Testers:

SnapDragon , Rustyoldman , marek.cygan , timmac , ivan_metelsky , Egor

Problem categories:

Dynamic Programming, Math