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.
Hard8Dynamic programmingCombinatoricsRecursionMathInterviewNo attempts yetTime limit2sMemory limit256 MBYoonyoung 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.
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 W, 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 H days is H 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 H days.
The first line contains H and W, separated by a space. 0≤H≤5 and 1≤W≤200.
Print, on the first line, the number of breeding patterns over H days modulo 1,000,000,007. 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.
For H=1 and W=3 the first microbe can produce 1, 2, or 3 children, which gives three patterns. Producing 0 children is ruled out by property 3.
For H=0 no breeding happens, so the only pattern is the empty one and the answer is 1.