C. Subsequence Counting

Pikachu 有一个数组，他将该数组的所有非空子序列写在了纸上。注意，一个大小为 $n$ 的数组有 $2^n - 1$ 个非空子序列。 Pikachu 一如既往地淘气，移除了所有满足 _子序列的最大元素_ $-$ _子序列的最小元素_ $\geq d$ 的子序列。 Pikachu 最终剩下 $X$ 个子序列。 然而，他丢失了原始数组，现在陷入严重困境。他仍然记得数字 $X$ 和 $d$。他现在希望你构造一个满足上述条件的任意数组。最终数组中的所有数字应为小于 $10^{18}$ 的正整数。 注意，输出数组的元素个数不应超过 $10^4$。如果无解，请输出 $-1$。 输入仅有一行，包含两个空格分隔的整数 $X$ 和 $d$（$1 \leq X, d \leq 10^9$）。 输出应包含两行。 第一行应包含一个整数 $n$（$1 \leq n \leq 10\,000$）——最终数组中整数的个数。 第二行应包含 $n$ 个空格分隔的整数——$a_1, a_2, \ldots, a_n$（$1 \leq a_i < 10^{18}$）。 如果无解，输出单个整数 $-1$。如果有多个答案，输出任意一个即可。 在第一个示例的输出中，移除所有满足 _子序列的最大元素_ $-$ _子序列的最小元素_ $\geq 5$ 的子序列后，剩余的子序列为 $[5], [5,7], [5,6], [5,7,6], [50], [7], [7,6], [15], [6], [100]$。共 $10$ 个，因此数组 $[5, 50, 7, 15, 6, 100]$ 是有效的。 类似地，在第二个示例的输出中，移除所有满足 _子序列的最大元素_ $-$ _子序列的最小元素_ $\geq 2$ 的子序列后，剩余的子序列为 $[10], [100], [1000], [10000]$。共 $4$ 个，因此数组 $[10, 100, 1000, 10000]$ 是有效的。 ## Input 输入仅有一行，包含两个空格分隔的整数 $X$ 和 $d$（$1 \leq X, d \leq 10^9$）。 ## Output 输出应包含两行。第一行应包含一个整数 $n$（$1 \leq n \leq 10\,000$）——最终数组中整数的个数。第二行应包含 $n$ 个空格分隔的整数——$a_1, a_2, \ldots, a_n$（$1 \leq a_i < 10^{18}$）。如果无解，输出单个整数 $-1$。如果有多个答案，输出任意一个即可。 [samples] ## Note 在第一个示例的输出中，移除所有满足 _子序列的最大元素_ $-$ _子序列的最小元素_ $\geq 5$ 的子序列后，剩余的子序列为 $[5], [5,7], [5,6], [5,7,6], [50], [7], [7,6], [15], [6], [100]$。共 $10$ 个，因此数组 $[5, 50, 7, 15, 6, 100]$ 是有效的。 类似地，在第二个示例的输出中，移除所有满足 _子序列的最大元素_ $-$ _子序列的最小元素_ $\geq 2$ 的子序列后，剩余的子序列为 $[10], [100], [1000], [10000]$。共 $4$ 个，因此数组 $[10, 100, 1000, 10000]$ 是有效的。

**Definitions** Let $ X, d \in \mathbb{Z}^+ $ be given integers with $ 1 \leq X, d \leq 10^9 $. We seek a finite sequence $ A = (a_1, a_2, \dots, a_n) $ of positive integers such that: - $ 1 \leq a_i < 10^{18} $ for all $ i $, - $ 1 \leq n \leq 10^4 $, - The number of non-empty subsequences $ S \subseteq A $ satisfying $ \max(S) - \min(S) < d $ is exactly $ X $. **Constraints** 1. $ 1 \leq X \leq 10^9 $ 2. $ 1 \leq d \leq 10^9 $ 3. $ n \leq 10^4 $ 4. $ a_i \in \mathbb{Z}^+ $, $ a_i < 10^{18} $ **Objective** Construct such a sequence $ A $, or output $-1$ if no such sequence exists. **Key Insight** A subsequence satisfies $ \max(S) - \min(S) < d $ if and only if all its elements lie within some interval of length $ < d $. Thus, if we partition the array into **groups** of elements where elements in the same group differ by less than $ d $, and elements from different groups differ by at least $ d $, then: - Any valid subsequence must be entirely contained within one group. - The number of valid non-empty subsequences is the sum over groups of $ (2^{g_i} - 1) $, where $ g_i $ is the size of group $ i $. **Strategy** We can construct $ A $ using disjoint clusters of identical elements (or elements within $ [v, v+d-1] $), each cluster contributing $ 2^{g} - 1 $ valid subsequences. Let $ X = \sum_{i=1}^k (2^{g_i} - 1) $, with $ g_i \geq 1 $, and $ \sum g_i \leq 10^4 $. Since $ 2^{30} > 10^9 $, we can represent $ X $ in binary: Write $ X = \sum_{j \in B} 2^j $, then $ X = \sum_{j \in B} (2^j - 1) + |B| $. So: $$ X = \sum_{j \in B} (2^j - 1) + |B| \Rightarrow \sum_{j \in B} (2^j - 1) = X - |B| $$ But we want $ X = \sum (2^{g_i} - 1) $, so we can directly use the **binary representation** of $ X $: Let $ X = \sum_{i=1}^k (2^{g_i} - 1) $, where each $ 2^{g_i} - 1 $ corresponds to a group of size $ g_i $. We can greedily decompose $ X $ as a sum of numbers of the form $ 2^k - 1 $: Note that $ 2^k - 1 $ is the number of non-empty subsequences of a group of $ k $ identical elements. We can use the greedy algorithm: While $ X > 0 $: - Find largest $ k $ such that $ 2^k - 1 \leq X $ - Add a group of $ k $ identical elements - Subtract $ 2^k - 1 $ from $ X $ Each group uses $ k $ elements, and $ k \leq \lfloor \log_2(X+1) \rfloor \leq 30 $, so total elements $ \leq 30 \cdot \log_2(X) \leq 30 \cdot 30 = 900 \ll 10^4 $, so feasible. To ensure $ \max(S) - \min(S) \geq d $ for cross-group subsequences, assign each group a distinct value spaced at least $ d $ apart. Set group $ i $ to have value $ v_i = i \cdot d $, and all elements in group $ i $ equal to $ v_i $. Then any two elements from different groups differ by at least $ d $, so any subsequence with elements from multiple groups has $ \max - \min \geq d $, and is removed. Thus, only intra-group subsequences survive. **Final Construction** Decompose $ X $ into a sum of terms $ 2^{k_i} - 1 $, for $ k_i \geq 1 $, using greedy selection of largest possible $ k $ such that $ 2^k - 1 \leq X $. For each such term, add $ k_i $ copies of $ i \cdot d $ (to ensure spacing $ \geq d $). If $ X = 0 $, invalid (but $ X \geq 1 $). **Edge**: If decomposition requires more than $ 10^4 $ elements, output $-1$. But since each $ k_i \leq 30 $ and $ X \leq 10^9 $, number of terms is at most $ \lceil X / 1 \rceil \leq 10^9 $, but we use greedy binary-like decomposition: the number of terms is at most the number of 1s in binary representation of $ X $, which is $ \leq 30 $. So total elements $ \leq 30 \cdot 30 = 900 $, safe. Thus, always possible unless decomposition fails? Actually, every $ X \geq 1 $ can be written as sum of $ 2^k - 1 $: since $ 2^1 - 1 = 1 $, we can always use $ X $ copies of group size 1. But that would require $ X $ elements, and $ X \leq 10^9 $, which exceeds $ 10^4 $. So we must use large groups. But greedy using largest possible $ k $ minimizes number of elements. **Algorithm** Initialize: - List `groups = []` - While $ X > 0 $: - Find largest $ k \geq 1 $ such that $ 2^k - 1 \leq X $ - Append $ k $ to `groups` - $ X \gets X - (2^k - 1) $ If total number of elements $ \sum k_i > 10^4 $, output $-1$. Otherwise, output array: for $ i = 1 $ to $ |groups| $, output $ \texttt{groups}[i] $ copies of $ i \cdot d $ **Note**: $ i \cdot d < 10^{18} $? Since $ i \leq 10^4 $, $ d \leq 10^9 $, so $ i \cdot d \leq 10^{13} < 10^{18} $, OK. **Output** - First line: $ n = \sum \texttt{groups} $ - Second line: $ \underbrace{i \cdot d, i \cdot d, \dots, i \cdot d}_{\texttt{groups}[i] \text{ times}} $ for $ i = 1, 2, \dots $ --- **Formal Output** **Definitions** Let $ X, d \in \mathbb{Z}^+ $ with $ 1 \leq X, d \leq 10^9 $. Let $ G = (g_1, g_2, \dots, g_m) $ be a sequence of positive integers such that: $$ X = \sum_{i=1}^m (2^{g_i} - 1) $$ and $ \sum_{i=1}^m g_i \leq 10^4 $. **Constraints** 1. $ 1 \leq X \leq 10^9 $ 2. $ 1 \leq d \leq 10^9 $ 3. $ g_i \geq 1 $ for all $ i $ 4. $ \sum_{i=1}^m g_i \leq 10^4 $ **Objective** Construct an array $ A = (a_1, a_2, \dots, a_n) $ where $ n = \sum_{i=1}^m g_i $, and: $$ a_j = i \cdot d \quad \text{for } j \text{ in the } i\text{-th group of size } g_i $$ such that the number of non-empty subsequences $ S \subseteq A $ with $ \max(S) - \min(S) < d $ is exactly $ X $. **Construction** Let $ X_0 = X $. Initialize $ G = [] $. While $ X_0 > 0 $: - Let $ k = \max \{ t \in \mathbb{Z}^+ \mid 2^t - 1 \leq X_0 \} $ - Append $ k $ to $ G $ - $ X_0 \gets X_0 - (2^k - 1) $ If $ \sum G > 10^4 $, output $-1$. Else, output: - $ n = \sum G $ - Array: for $ i = 1 $ to $ |G| $, output $ G[i] $ copies of $ i \cdot d $ (Note: $ i \cdot d < 10^{18} $ holds since $ i \leq |G| \leq 10^4 $, $ d \leq 10^9 $, so $ i \cdot d \leq 10^{13} $)