Sequence Construction (USACO Silver 2025 Open)

初看没什么思路，这种没思路的题，要不贪心，要不反着想，题目名字中间又有“construction”，所以考虑一下贪心法来构造。

首先，我们可以看到， $K$ （popcount xor）如果每个二进制位是仅由一个数来贡献的最简单的情况：比如例子中的 $K=5$ ，由 $2^2=4$ , $2^0=1$ 两个二进制位组成，那对应的就是 $\text{popcount}(a_1)=4$ ， $\text{popcount}(a_2)=1$ ，这时 $a_1$ 最小值是 $15$ ， $a_2$ 最小值是 $1$ 。这时我们可以注意到， $s=15+1=16$ 是 $K=5$ 时最小的可能的 $M$ ，这就解决了例子中的第三个“10 5”是不可能的，因为 $M$ 最小需要是 $15$ 。

看起来有点意思了，我们找到了一个构造 $M$ 的最小值 $s$ 的办法。那么对于通用的情况，就是剩下的数值 $M-s$ 怎么处理的问题。还是考虑 $M-s$ 中的二进制位，我们需要在不改变popcount xor的情况下，构造出 $M-s$ 对应的二进制位。有一些情况很简单，比如 $M-s$ 由偶数个二进制位组成（这也是sub task 2中间 $M > 2^K$ 提示的情况），就是把每位变成一个数字就行，这时他们的popcount都是1，XOR在一起后就是0，不改变popcount xor。有些情况复杂一些。根据这个思路，我们得到以下构造算法：

对于 $K$ 中的每一位 $d_i$ ，使用 $2^{d_i}-1$ ，来生成 popcount xor 最小的 $a$ 序列
$s=\sum a_j$
如果 $M=s$ ， $a_j$ 就是答案
如果 $M < s$ ，输出 $-1$
如果 $M \geq s+2$ ，则生成 $M-s$ 所有二进制位对应的数，如果是偶数个，与上面的 $a$ 合并后就是答案。如果是奇数个，则把最高位分成两半，就可以了。
特殊情况是 $M=s+1$ 。如果 $K$ 是奇数， $s+1$ 是可行的，只需要把 $a$ 中的 $1$ 变成 $2$ ，如果是偶数，则 $s+1$ 不可行，输出 $-1$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t,m,k;
 
int main() {
    scanf("%d", &t);
    while (t--) {
        int s = 0;
        vector<int> a;
        scanf("%d %d", &m, &k);
        for (int i = 0; i < 6; i++) {
            int d = 1 << i;
            if (k & d) {
                s += (1 << d) - 1;
                a.push_back((1 << d) - 1);
            }
        }
        if (m < s) {
            printf("-1\n");
            continue;
        }
        m -= s;
        int pm = __builtin_popcount(m);
        if (m == 1) {     // special case: s+1
            if (a[0] == 1) {
                a[0] = 2;
            } else {
                printf("-1\n");
                continue;
            }
        } else {          // general case
            for (int i = 0; i < 31; i++) {
                if (1 << i & m)
                    a.push_back(1 << i);
            }
            if (pm % 2) { // split highest bit if remaining number is popcount odd
                int tmp = a.back();
                a.pop_back();
                a.push_back(tmp / 2);
                a.push_back(tmp / 2);
            }
        }
        printf("%d\n", a.size());
        for (int i = 0; i < a.size(); i++) {
            printf("%d ", a[i]);
        }
        printf("\n");
    }
    return 0;
}