Accepted Contest Solution (With Syntax Fixes).

Source: http://8.136.99.126/record/67ff11b57aadac7b413bd2ff

Author:

令 $A \in \{ 0, 1 \}$，则 $1\sharp A=A$，$0 \sharp A=1$。

即如果 $A=1$ 状态保持 $1$；如果 $A=0$ 状态变为 $0$。

定义 $f(0)=1, f(i)= f(i-1)\sharp A_i, 1\leq i\leq N$，我们需要统计 $f(N)=1$ 的串的个数。

定义 $G(N)$ 为从初始状态 $1$ 出发，经过长度为 $N$ 的 01 串最终状态为 $1$ 的串的个数。

$G(0)=1$（显然），$G(1)=1$（$1 \sharp A = A$，只有 $A=1$ 可以使 $f(1)=1$）。

考虑 $N\ge2$，从初始状态 $1$ 出发，经过长度为 $N$ 的 01 串 $A_1A_2\cdots A_N$。我们讨论串的第一位 $A_1$ 的两种情况：

第一位为 $1$：

• 初始状态 1 经 $1\sharp1$ 得到 $f(1)=1$。
• 此时余下的串 $A_2\cdots A_N$ 长度为 $N-1$，问题变为「从状态 $1$ 出发读入 $N-1$ 位 01 串，使最终状态为 $1$」。
• 这种情况的串数为 $G(N-1)$。

第一位为 $0$：

• 初始状态 $1$ 经 $1\sharp0$ 得到 $f(1)=0$。
• 接下来读入 $A_2$ 时，由于当前状态为 $0$，有 $f(2)=0\sharp A_2=1$。
  且无论 $A_2$ 取 $0$ 或 $1$（即有 $2$ 种选择），状态都变为 $1$。
• 此后余下的串 $A_3\cdots A_N$ 长度为 $N-2$，要求从状态 $1$ 出发最终状态为 $1$，对应的串数为 $G(N-2)$。
• 综上，这种情况的串总数为 $2\times G(N-2)$。

两类情况互不重叠且覆盖所有长度为 $N$ 的 01 串，因此 $G(N)=G(N-1)+2\times G(N-2)$。