Counting Base Representations
Time limit2sMemory limit128 MB
Count the ways to split a digit string into a base suffix and a sequence of no-leading-zero digit values all less than that base.
- Level
Medium7 of 10
- Topics
- Dynamic programming, String, Combinatorics
- Solved
- No attempts yet
Problem
A string S consisting only of decimal digits is given. Count how many ways parentheses and spaces can be restored so that the string becomes a valid base representation.
A representation is defined as follows.
- A nonempty suffix of the string is used as the base
b. The base must be an integer at least 2 and must not have unnecessary leading zeros. - The preceding nonempty prefix is split into one or more digit values. Each digit value is written in decimal and must satisfy
0 <= d < b. - A digit value must not have unnecessary leading zeros. The value zero may be written only as the single string
0.
Even if two representations denote the same numeric value, they are counted separately when their split positions are different.
Input
The first line contains a string S consisting only of decimal digits. The length of S is at most 35.
Output
Print the number of possible representations.