题解

思路

$N\le3$ 时答案恒为 1。

做法

先考虑 $c_{\mathrm{AB}}=\texttt{B}$：若 $c_{\mathrm{BB}}=\texttt{B}$，始终只有一个字符串；否则若 $c_{\mathrm{BA}}=\texttt{A}$，恰能得到所有以 AB 开头、以 B 结尾的字符串，答案为 $2^{N-3}$；若 $c_{\mathrm{BA}}=\texttt{B}$，可达字符串还要求不含连续两个 A，数量满足初值均为 1 的 Fibonacci 递推，答案为 $F_{N-2}$。

当 $c_{\mathrm{AB}}=\texttt{A}$ 时，同时交换 A/B 并反转字符串即可化为前一种情况，此时分别检查 $c_{\mathrm{AA}}$ 与 $c_{\mathrm{BA}}$。

复杂度

预处理 Fibonacci 并快速幂即可，时间复杂度为 $O(N+\log N)$，空间复杂度为 $O(N)$。