TopCoder problem "SequencePermutation" used in TCO10 Wildcard (Division I Level One)



Problem Statement

    You are given a sequence 1, 2, .., N. M times, you pick two adjacently located numbers in the sequence and swap them. Return the number of different final sequences that can be obtained modulo 1,000,000,009.
 

Definition

    
Class:SequencePermutation
Method:determineConfigurations
Parameters:int, int
Returns:int
Method signature:int determineConfigurations(int N, int M)
(be sure your method is public)
    
 

Constraints

-N will be between 2 and 2000, inclusive.
-M will be between 0 and 2000, inclusive.
 

Examples

0)
    
3
1
Returns: 2
The possible resulting sequences are (1,3,2) and (2,1,3).
1)
    
3
0
Returns: 1
The only possible resulting sequence without swapping any of the elements is the original sequence, that is, (1,2,3).
2)
    
3
3
Returns: 3
3)
    
33
1803
Returns: 620284697
Watch out for integer overflow!

Problem url:

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

Problem stats url:

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

Writer:

dolphinigle

Testers:

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

Problem categories:

Dynamic Programming