CF8E 题解

blog。抽象意义上单杀了。

首先第一位必定为 \(0\)，然后取反串就不用去考虑了。

\(n\le50\)，考虑爆搜。搜整个串的前一半（设半长为 \(M=\left\lfloor\dfrac n2\right\rfloor\)，前一半的串在十进制下值为 \(v\)），后半段的数量可以计算：

• 整个串最后一位是 \(0\)，只需满足逆序串。\(n\) 为偶数时方案数为 \((2^{M-1}-v)\)，\(n\) 为奇数时方案数为 \(2(2^{M-1}-v)\)。
• 整个串最后一位是 \(1\)，只需满足逆序取反串。\(n\) 为偶数时方案数为 \((2^{M-1}-v)\)，\(n\) 为奇数时方案数为 \((2^{M-1}-v-1)\)。
• 总的来说，\(n\) 为偶数时方案数为 \(2(2^{M-1}-v)\)，\(n\) 为奇数时方案数为 \(2(2^{M-1}-v)+(2^{M-1}-v-1)\)。

持续累加合法数量，显然可以找到前一半的答案。然后爆搜后一半的答案即可。

一些细节：全选 \(0\) 是不合法的，为了方便可以在最开始 \(k\gets k+1\)；维护串时请在全局用数组模拟，use string record。

code，时间复杂度 \(O(n2^n)\)，瓶颈在后半段的爆搜，替换成二分可以做到 \(O(2^n)\)。