CF1965B Missing Subsequence Sum

以下区间默认整数区间。

要求构造 $[1, k) \cup (k, n]$。

若没有 $k$ 的限制，可以在二进制下构造。具体地，构造出 $2^0, 2^1, 2^2, \dots$。在选取子序列的时候相当于枚举二进制的每一位选或不选，从而能构造出所有数。

对于 $[1, k)$ ，相当于没有限制的情况下构造，设 $d = \lfloor \log _2 k \rfloor$，则构造的序列为 $\{2 ^ 0, 2 ^ 1, 2 ^ 2, \dots, 2 ^ {d - 1}, k - 2 ^ d\}$。加入 $k - 2^d$ 是因为我们已经构造出了集合 $S_0 = [1, 2 ^ d)$，若此时添加一个数 $y$，钦定必须选 $y$，则新的集合为 $S_1 = \{x \in \mathbb{N} ^+ | x = y + p, p \in S_0 \cup 0\}$，$y$ 可以不选，所以加入 $y$ 后的集合为 $S_0 \cup S_1$。

构造出了 $[1, k)$ 考虑如何构造 $(k, n]$。发现 $[k, n]$ 中任何数都可以表示为 $ak + b$，其中 $a \in \mathbb{N} ^ +, b \in [0, k)$。但是 $k$ 是我们不希望构造的，于是考虑先构造 $(k, 2k]$，再构造后面的 $a'k + b,(a' \in [2, +\infty ] \cup \mathbb{Z})$。由上面的结论，加入 $k + 1$ 可以使能构造的集合变为 $[1, k) \cup (k, 2k]$，此时只需要添加 $2 ^ i k, i \in \mathbb{N} ^+$，直到 $2^ik \ge n$ 即可。

为什么要构造 $2^ik$？用 $2^i$ 是因为我们在构造 $k$ 前面的系数 $a$，根据构造 $[1, k)$ 时的操作，我们同样枚举 $a$ 的二进制下的位数便可构造出连续的一段数字。

次数为 $\log_2 n$ 量级。