Contest Duration: - (local time) (100 minutes) Back to Home

## 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: