SequencePermutation
TCO10 Wildcard · 2010-04-11 · by dolphinigle
TCO10 Wildcard · 2010-04-11 · by dolphinigle · Dynamic Programming
Problem Statement
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.
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!
4)
2000 2000 Returns: 624672242
Submissions are judged against all 178 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SequencePermutation with a public method int determineConfigurations(int N, int M) · 178 test cases · 2 s / 256 MB per case