Hardcore String Counting 2

시간 제한2초메모리 제한512 MB

요약

알파벳 {a, b, c}로 이루어진 길이 1부터 n까지의 제곱 없는 단어 개수를 각각 구합니다. n은 120 이하입니다.

난이도: 어려움10점 중 8점
유형: 문자열, 백트래킹, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

"Hardcore String Counting 1"은 어떻게 되었을까? 비밀이다! 어떤 알파벳 위의 비어 있지 않은 단어 $v$ 가 어떤 단어 $w$ 에 대해 $v = ww$ 로 나타낼 수 있으면 $v$ 를 제곱이라고 한다. 단어의 모든 비어 있지 않은 부분 문자열이 제곱이 아니면, 그 단어를 제곱 없는 단어라고 한다. 알파벳 {a, b, c}로 만들 수 있는 길이 $\ell$ 인 제곱 없는 단어의 개수를 $\ell = 1$ 부터 $n$ 까지 각각 구하라.

입력

입력은 정수 $n$ ( $1 \leq n \leq 120$ ) 한 줄로 주어진다.

출력

$\ell$ 을 1부터 $n$ 까지 각각 출력한다. 각 $\ell$ 에 대해 알파벳 {a, b, c}로 이루어진 길이 $\ell$ 인 제곱 없는 단어의 개수를 별도의 줄에 출력한다.

힌트

더 자세한 내용은 https://oeis.org/A006156를 참고하라. 다만 이 자료가 풀이에 별로 도움이 되지 않을 것이다.

예제1

예제 1
입력
```
10
```
예상 출력
```
3
6
12
18
30
42
60
78
108
144
```