Alien microbes
InterviewTime limit2sMemory limit256 MB
Count the breeding patterns over H days starting from one microbe, where each day the microbes alive produce children with a total of at most W.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Combinatorics, Recursion, Math
- Solved
- No attempts yet
Problem
Yoonyoung looked at a transcript full of B and C grades, decided she had no talent for computer science, switched to a double major in aerospace engineering and biology, and became a successful researcher of alien life.
On one planet she found an unusual alien microbe and carried a few of them back to her lab. Her study showed that the microbe has the following properties.
- A microbe produces children on its own. It produces all of its children during one day and dies that same day. Each microbe freely decides how many children to produce. Children are told apart by the order in which they are produced, and a child starts producing children of its own on the day after it is born.
- The microbes do not want their children to compete too hard with each other. They cooperate so that the total number of children produced by the microbes alive on a given day is at most . The value of stays the same across generations.
- A microbe may produce no children at all, but to keep the species going the case where every microbe alive that day produces no children never happens. A microbe that produces no children still dies the day after it was born.
Yoonyoung enjoyed watching this creature breed, so she put a single microbe into a container in her lab. In that container the total number of children allowed without too much competition is , and the microbe started breeding.
Microbes alive on the same day are told apart from each other. The pattern of one day is the sequence of child counts of the microbes alive that day, written in the order of the microbes, and a pattern over days is such sequences listed in day order. Two patterns count as different if they differ on any day.
Starting from a single microbe, count the breeding patterns that can appear over days.
Input
The first line contains and , separated by a space. and .
Output
Print, on the first line, the number of breeding patterns over days modulo . The count grows large, so an intermediate value can exceed the range of a 32 bit integer. A 64 bit integer is the safe choice.
Hint
For and the first microbe can produce 1, 2, or 3 children, which gives three patterns. Producing 0 children is ruled out by property 3.
For no breeding happens, so the only pattern is the empty one and the answer is 1.