진법 표현 세기
시간 제한2초메모리 제한128 MB
숫자 문자열을 진법을 나타내는 접미사와 그 진법보다 작은 값들로 이루어진 접두사로 나누는 방법의 수를 구하는 문제입니다.
문제
숫자로만 이루어진 문자열 S가 주어진다. 이 문자열에 공백과 괄호를 다시 넣어 어떤 진법 표현을 만들 수 있는지 세어야 한다.
하나의 표현은 다음과 같이 정해진다.
- 문자열의 마지막 일부를 진법
b로 사용한다.b는 2 이상의 정수이며, 불필요한 앞자리 0이 없어야 한다. - 그 앞부분은 하나 이상의 자리 값으로 나눈다. 각 자리 값은 10진수로 쓴 정수이며
0 <= d < b를 만족해야 한다. - 자리 값도 불필요한 앞자리 0을 가질 수 없다. 단, 값이 0인 자리 값은 문자열
0하나로 쓸 수 있다.
실제로 나타내는 수의 값이 같더라도, 나누는 위치가 다르면 서로 다른 표현으로 센다.
입력
첫째 줄에 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 35 이하이다.
출력
가능한 표현의 개수를 출력한다.