Standard Solution.

若某个 01 串 $A$ 不满足第二个条件：

$$A_1\sharp(A_2\sharp(A_3\sharp(\cdots\sharp(A_{N-1}\sharp A_N))))=0 $$$$A_2\sharp(A_3\sharp(\cdots\sharp(A_{N-1}\sharp A_N)))=0\ (A_1=1) $$$$A_3\sharp(\cdots\sharp(A_{N-1}\sharp A_N))=0\ (A_2=1) $$$$\ldots$$ $$A_{N-1}\sharp A_N=0$$

因此只有 $S=\tt{111\ldots110}$ 不满足第二个条件。很明显，$S$ 同时也不满足第一个条件，所以第二个条件实际上是多余的。

对于第一个条件，设答案为 $f(N)$：

• 如果 $A_N=1$，那么一定满足条件，共有 $2^{N-1}$ 个合法 01 串；
• 如果 $A_N=0$，那么需要有 $((((A_1\sharp A_2)\sharp A_3)\sharp\cdots)\sharp A_{N-2})\sharp A_{N-1}=0$，共有 $2^{N-1}-f(N-1)$ 个合法 01 串。

结合 $f(1)=1$，我们得到了 $f(N)$ 的递推公式：

$$f(N)=\begin{cases}1,&N=1\\2^N-f(N-1),&N\ge 2\end{cases} $$

由数学归纳法即可证明通项公式。

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)$。