前言

把此题放到 T4 然后模拟考最为期末成绩，目前感觉快 AFO 了。最后 $20 + 100 + 20 + 10 = 150pts$。想要考试的四道原题的家人们可以私信我要题号。

解题思路

防止读者在阅读时忘记 $\text{popcount}(x)$ 时什么意思，所以就放在这里了。

$\text{popcount}(x)$ 表示整数 $x$ 的二进制表示中 $1$ 的位数。例如，$\text{popcount}(11) = 3$，$\text{popcount}(16) = 1$。

乍眼一看似乎很不可做的样子，实则因人而异。

赛时看到异或，首先想到 01trie，然后想了一阵发现不会，于是就没想了。

赛后瞅一眼题解，发现了一条重要性质：$\text{popcount}(1) = \text{popcount}(2)$。我赛时怎么没想到！

相信大家看到题目可能会先想着去构造序列 $a$，使得其满足 $a_1 + a_2 + \cdots + a_N = M$ 吧，但是这样很难再进行构造使得 $\text{popcount}(a_1) \oplus \text{popcount}(a_2) \oplus \cdots \oplus \text{popcount}(a_N) = K$，所以我们可以先使得其满足条件 $3$，再来想办法让其满足条件 $2$。

我们先构造一个满足条件的序列 $a$，使此序列的和最小（不是异或和）。其实我们并不需要考虑类似 $x\oplus x = 0, x \oplus x \oplus x = x$ 的情况，我们要求和最小就是为了避免初步构造时出现上述复杂情况（因为如果这些数的某一位上重复出现很多次 $1$，那么它们的总和一定不是最小的，我们可以使得这一位只出现 $0$ 次或 $1$ 次 $1$ 来达到同样的效果），即我们需要一步一步来，不能做到一步到位。

怎么构造和最小且满足条件 $3$ 的序列呢？想到异或与二进制有关，因此可以考虑对于 $K$ 进行二进制分解。这一步可能有点绕且难以描述，所以我们以第二组数据进行模拟再进行解释。

$M = 33, K = 5$，首先二进制分解 $K$ 得到 $(101)_2$，向答案数组里面添加 $2^4 - 1, 1$，因为第一个 $1$ 代表 $2^2 = 4$，所以得到 $2^4 - 1$。

为什么要这么做？别忘了 $K$ 代表的是所有数在二进制下 $1$ 的个数的和，那么将其二进制拆分则代表第 $1$ 个数的 $1$ 的个数为 $4$，那么最小的数即 $(1111)_2 = 2^4 - 1$。

那么我们选出来的这些数即我们的初始元素。将 $M$ 减去这些数的和，记为 $M_2$。

• 如果 $M_2 < 0$，显然无解。
• 否则如果 $M_2 = 0$，那么我们构造的 $a$ 已经同时满足条件 $1,2$ 了，直接输出即可。
• 否则如果 $M_2 = 1$，则我们还差 $1$ 才能同时满足条件 $1,2$。
• • 如果已构造出来的序列中有 $1$，由于 $\text{popcount}(1) = \text{popcount}(2)$，所以我们可以将序列中的 $1$ 变成 $2$ 来达到条件。
• • 如果已构造出来的序列中没有 $1$，那么一定无解，因为不存在某个数与序列中的所有数同时满足为 $2^i,2^j$ 且 $|2^i - 2^j| = 1$。
• 否则如果 $M_2$ 为偶数，直接往答案序列中加入两个 $\frac{M_2}{2}$ 即可（两个相同的数异或后值为 $0$，不影响条件 $3$）。
• 否则即 $M_2$ 为奇数，由于 $\text{popcount}(1) = \text{popcount}(2)$ 且 $M_2 \geq 3$（$M_2 = 1$ 的情况处理过了），因此我们可以从 $M_2$ 中取出来一个 $1$ 和 $2$ 就可以将 $M_2$ 转化为偶数的情况。（因为取出来一个 $2$ 虽然可能会导致 $M_2$ 的二进制排列差异过大，但是取出来一个 $1$ 和 $2$ 过后，后面两个数都为 $\frac{(m - 3)}{2}$，异或后为 $0$，前面只有 $1,2$ 且 $\text{popcount}(1) \oplus \text{popcount}(2) = 0$，所以 $0 \oplus 0 = 0$，$1 + 2 + \frac{(m - 3)}{2} \times 2 = M_2$，所以此方案可行。）

对于条件 $1$ 就懒得说了，大家可以看看代码，满打满算 $5 + 1 + 4 = 10 < 100$。

如果本题解有什么写错的地方可以在评论区踹我一脚，我好修改，没看懂的也可以踹我一脚，我好写得更详细。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> v;
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int m, k, sum = 0;
		cin >> m >> k;
		bool flag1 = false;
		v.clear();
		for (int i = 5; i >= 1; i--) {
			int p = (1 << i);
			if (k >= p) {
				k -= p;
				v.emplace_back((1 << p) - 1);
       //emplace_back = push_back，据说跑得要快点而已。
				sum += (1 << p) - 1;
			}
		}
		if (k) {
			flag1 = true;
			v.emplace_back(1);
			sum++;
		}
		if (sum > m) {
			cout << "-1\n";
			continue;
		}
		m -= sum;
		if (m == 1) {
			if (flag1) {
				v.pop_back();
				v.emplace_back(2);
			} else {
				cout << "-1\n";
				continue;
			}
		} else if (m) {
			if (m & 1) {
				v.emplace_back(1);
				v.emplace_back(2);
				if (m > 3) {
					v.emplace_back((m - 3) / 2);
					v.emplace_back((m - 3) / 2);
				}
			} else {
				v.emplace_back(m / 2);
				v.emplace_back(m / 2);
			}
		}
		cout << v.size() << "\n";
		for (auto u : v) {
			cout << u << ' ';
		}
		cout << "\n";
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
const int N=40;
int d[N],d1[N];
int highbit(int x){int sum=0;for(int i=0;i<31;i++)if((x>>i)&1)sum=i+1;return sum;}
void init(){d[0]=1;for(int i=1;i<=31;i++)d[i]=d[i-1]<<1;for(int i=1;i<=31;i++)d1[i]=d1[i-1]+d[i-1];}
vi nan(){vi ans;ans.push_back(-1);return ans;}
int get(int x){return 1<<(highbit(x)-1);}
vi solve(int x,int k)
{
    vi ans;
    if(k==1&&x==2)
    {
        ans.push_back(2);
        return ans;
    }
    if(k==0)return nan();
    if(x>=d1[k])
    {
        int sum=x-d1[k];ans.push_back(d1[k]);
        if(sum==0)return ans;
        if(sum%2==0)
        {
            ans.push_back(sum/2);
            ans.push_back(sum/2);
            return ans;
        }
        if(sum%2==1&&sum!=1)
        {
            ans.push_back(1);
            ans.push_back(2);
            sum-=3;if(sum==0)return ans;
            ans.push_back(sum/2);
            ans.push_back(sum/2);
            return ans;
        }
    }
    ans.clear();
    if(x>=d1[get(k)])
    {
        int sum=x-d1[get(k)];
        vi res=solve(sum,k-(1<<(highbit(k)-1)));
        if(res.empty())return nan();
        if(res[0]==-1)return nan();
        ans.push_back(d1[get(k)]);
        for(int y:res)ans.push_back(y);
        return ans;
    }
    return nan();
}
int main()
{
    init();
    int t;cin>>t;
    while(t--)
    {
        int x,k;cin>>x>>k;
        vi ans=solve(x,k);
        if(ans.empty()||ans[0]==-1)puts("-1");
        else
        {
            cout<<ans.size()<<'\n';
            for(int y:ans)cout<<y<<" ";
            cout<<'\n';
        }
    }
    return 0;
}