A002894

注意特判 n=1。

先进行必要的特判，小数据判掉，不是 $4k+1$ 判掉。

把所有合法串打出来。先不管 $1$ 开头的那些串，结尾乘 $2$ 即可。然后我们把开头和结尾的两个 $0$ 剥离，此时使用注意力发现答案相当于在 $n-2$ 个位置里放 $\frac{n-1}{4}$ 段球，球的总数是 $\frac{n-1}{2}$，且两段球之间必须有至少一个空隙。

使用插板法，将每段后面第一个 $0$ 和这一段绑在一起，并在结尾添加一个虚拟的 $0$，推导出答案的公式是

$$2\binom{\frac{n-1}{2}-1}{\frac{n-1}{4}-1}\binom{n-2-(\frac{n-1}{2}-\frac{n-1}{4})-\frac{n-1}{4}+1}{\frac{n-1}{4}}$$

化简即可得到 $\binom{\frac{n-1}{2}}{\frac{n-1}{4}}^2$。