21352번 - Fibonacci Strings 다국어언어 제한함수 구현

문제

Aron likes Fibonacci numbers. He likes them so much he actually got bored of the numbers themselves and decided to invent other combinatorial objects based on them instead.

His first invention is the Fibonacci string. We call a string consisting of only letters $a$ and $b,ドル with exactly $n$ letters $a$ without any two consecutive letters $a$ a Fibonacci string of the $n$:th order.

Given a string $X$ of $a$:s and $b$:s, compute the sum of orders of all Fibonacci strings that are substrings of $X$. Note that if a string $X$ appears multiple times, its order should be counted once for every occurance.

예제

Assume that Aron has the string $abaaba$. This contains the Fibonacci string $a$ four times, $ab$ two times, $ba$ two times and $aba$ two times. The sum of their orders is 4ドル \cdot 1 + 2 \cdot 1 + 2 \cdot 1 + 2 \cdot 2 =わ 4 +たす 2 +たす 2 +たす 4 =わ 12$.

구현

Write a program that given $X$ computes the sum of orders of all Fibonacci substrings of $X$. You should implement the function fibonacci(N, X}.

• fibonacci(N, X) - this function will be called exactly once by the judge.
  • N: an integer - the number of charaters in the string $X$.
  • X: a string consisting of $X$ characters, consisting only lowercase letters $a$ and $b$.
  • The function should return an integer, the sum of orders of all Fibonacci substrings of $X$.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at attachments.zip.

입력

The sample judge reads input in the following format:

• line 1ドル$: N
• line 2ドル$: X

출력

The judge writes a single line containing the return value of fibonacci(N, X).

제한

• 1ドル \le N \le 100,000円$

힌트