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 量级。