CF1966D Missing Subsequence Sum 题解

题意：给定 \(n(n \le 10^6)\) 和 \(k(k \le n)\)。构造一个长度小于等于 \(25\) 的序列 \(a\) 满足：
1. 不存在一个子序列的和为 \(k\)。
2. 对于 \(1 \le i \le n,i \ne k\)，存在一个子序列的和为 \(i\)。

看到长度为 \(25\)，首先肯定会想到二进制。那么我们先构造出一个序列 \([2^0,2^1,\dots,2^{19}]\)，会发现这样一定可以表示出所有 \(1\) 到 \(n\) 的数。但是要求不能表示出 \(k\)，所以我们把 \(2^p\) 删掉，其中 \(p\) 是 \(k\) 的最高位。

删掉之后会出现一个问题，除了 \(k\) 之外且第 \(p\) 位为 \(1\) 的数也不能表示出来了，考虑如何解决。

一个结论是：再加上 \(k-2^p,k+1,k+1+2^p\) 这三个数，最终的序列一定合法。