AU7_5 - STUDENTS
Professor X wants to position N (1 <= N <= 100,000) girls and boys in a single row to present at the annual fair.
Professor has observed that the boys have been quite pugnacious lately; if two boys too close together in the line, they will argue and begin to fight, ruining the presentation. Ever resourceful, Professor calculated that any two boys must have at least K (0 <= K < N) girls between them in order to avoid a fight.
Professor would like you to help him by counting the number of possible sequences of N boys and girls that avoid any fighting. Professor considers all boys to be the same and all girls to be the same; thus, two sequences are only different if they have different kinds of students in some position.
Input
First line contains C (1 <= C <= 20) the number of test cases.
Next C lines contain N and K.
Output
A single integer representing the number of ways Professor could create such a sequence of students. Since this number can be quite large, output the result modulo 5000011.
Sample
Input 1 4 2 Output 6
Explanation
The possible sequences are GGGG, BGGG, GBGG, GGBG, GGGB, or BGGB.
hide comments
amirmb:
2020-12-02 09:45:44
nice dp problem :) |
|
Irfan:
2018-01-08 08:22:20
Got WA in topdown but AC in bottom up :(
|
|
Rishav Goyal:
2014-06-07 15:19:57
learnt something new :) |
|
Man Mohan Mishra:
2013-05-31 13:32:05
awesome problem !!
|
|
fitcat:
2013-05-31 06:20:15
My 500th completed classical problem :) |
Added by: | arun |
Date: | 2013-05-08 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: BF |