## D - AB Editorial by evima

The answer is obviously \(1\) for \(N = 2, 3\). Below, we assume \(N>3\).

Let us consider the case \(c_{\mathrm{AB}} =\) `B`

. (The case \(c_{\mathrm{AB}} =\) `A`

is almost the same.)

If \(c_{\mathrm{BB}} =\) `B`

, there is only one string that can be made.
Below, we assume \(c_{\mathrm{BB}} =\) `A`

.

If \(c_{\mathrm{BA}} =\) `A`

here, we can construct every string that begins with `AB`

and ends with `B`

, so the answer is \(2^{N-3}\).

If \(c_{\mathrm{BA}} =\) `B`

, among the strings that begin with `AB`

and end with `B`

, we can construct everything that does not contain `AA`

as a substring. In this case, the answer is \(F_{N-2}\), where \(F\) is defined as follows:

\( F_{n} = \begin{cases} 1 & \text{if } n \leq 1 \cr F_{n-1} + F_{n-2} & \text{otherwise} \end{cases}\)

posted:

last update: