Boxes and Stones
Time limit1sMemory limit128 MB
Count the initial distributions of S indistinguishable stones among the first B-1 boxes from which Carole, moving second each round, can force a win against Paul.
- Level
Hard8 of 10
- Topics
- Game theory, Combinatorics, Dynamic programming, Prefix sum
- Solved
- No attempts yet
Problem
Paul and Carole play a game with stones and boxes numbered from to . Before the game begins, the stones are distributed arbitrarily among boxes through , leaving box empty. The game then proceeds in rounds.
In each round, Paul first chooses a subset of the stones currently in the boxes; he may take as many stones as he wants from as many boxes as he wants, or none at all, in which case is empty. Then Carole decides between two actions:
- promote and discard the remaining stones, or
- discard and promote the remaining stones.
To promote a stone means to move it to the box with the next number, so a stone in box moves to box . To discard a stone means to remove it from its box permanently, so it is not used in any later round.
Play continues until some stone reaches box , in which case Paul wins, or until no stones remain in the boxes, in which case Carole wins. Both players play optimally. Count the number of initial distributions of the stones among boxes through for which Carole can be certain of winning, even if Paul never makes a mistake.
Input
The input consists of several test cases, one per line, until end of file. Each line contains two integers and (, ), the number of stones and the number of boxes.
Output
For each test case, print on its own line the number of ways to distribute the stones among the first boxes so that Carole is certain to win. Because this number can be very large, print it modulo .