Number of Trees
Time limit2sMemory limit128 MB
Count the number of rooted ordered trees whose DFS-with-repeated-parent-writes traversal string equals a given string, modulo 1e9.
- Level
Hard8 of 10
- Topics
- Dynamic programming, String, Combinatorics
- Solved
- No attempts yet
Problem
There is a rooted ordered tree. Each vertex has one uppercase English letter written on it, and the same letter may appear on multiple vertices.
The traversal starts at the root. Whenever the traversal arrives at a vertex, it writes that vertex's letter to the path. Then it visits the unvisited children of that vertex from left to right, one at a time. After finishing one child and returning to its parent, the parent's letter is written again. Therefore, a vertex with children may appear in the path several times.
Given an uppercase path string, count how many rooted ordered trees produce exactly that path. Trees with different left-to-right child order are counted as different trees.
Input
The first line contains the path string. It consists only of uppercase English letters, and its length is at most 300.
Output
Print the number of possible trees modulo 1,000,000,000.