题解：P13617 [ICPC 2025 APC] Bit Counting Sequence

Gordon_Song · 2025-09-22 19:27:39 · 题解

容易发现 a_p-a_{p-1} \leq 1，否则一定无解。因此开始分类讨论。

对于 a_p = a_{p-1} +1，那么说明 x+p-1 是奇数。

否则说明 a_{p-1} 后面有 a_p - a_{p-1} +1 是 1，同时从小往大的第 a_p - a_{p-1} +2 是 0。

也就是说，我们现在有若干个限制，每个限制形如 x + i -1 最后的若干位为 1，前面还强制有一个 0。因此，不妨设 k 为 a 中最大值所处的位置，那么我们可以知道 x+p-1 一定是 11\dots11011\dots1（一共有 a_k 个 1），这是因为前面的位置不会再影响正确性了，所以直接在最前面紧凑地填上 1。

然后就判断一下这个数是否满足条件就可以了。

唯一的特殊情况是 k = n 时，答案为 2^{a_n}-n，自证不难。