orz zjk。学到了。对于这一类计数最终由多少不同局面的题，我们首先应当考虑一下如何判断最终局面合法。感觉正着做不太方便，于是我们考虑倒着做。
首先，容易发现 0 和 1 是对称的，哪个是 0 哪个是 1 不重要，所以我们不妨设 。
考虑倒着操作是怎么样的，于是我们将操作改写为：
- 选择 中长度为 的字串，其中字符为 0 或 ?，将他们改为 ?。
- 选择 中长度为 的字串，其中字符为 1 或 ?，将他们改为 ?。
容易发现，我们只要最后到达了全是 0 或者 ? 的字符串就有解了。观察并手玩一下，发现只要进行了一次二操作，就一定有解。原因是进行一次二操作后我们可以得到一个长度为 的 ? 区间。我们必定可以通过每次往左，往右拓展一格使得整个字符串被置为 ?。
到这里有解的限制就变得清晰了。一个最终局面 有解当且仅当将其长度大于等于 的字串置为 1之后，1 的极长连续段的长度大于等于 。
现在你可以直接计数了。这部分是简单的。
