Subtask 1:

We can enumerate all the arrays that sum to $M$ in $O(M2^M)$ time and check if any of them satisfy the conditions in the problem statement.

My C++ code:

#include <iostream>
#include <vector>

using namespace std;

int flag;

vector<int> ans;

int popcount(int x){
	if(x == 1 || x == 2 || x == 4) return 1;
	if(x == 7) return 3;
	return 2;
}

void dfs(int m, int k){
	if(m == 0 && k == 0){
		flag = 1;
		return ;
	}
	if(!flag){
		for(int i = 1; i<=m; i++){
			ans.push_back(i);
			dfs(m - i, k^popcount(i));
			if(flag) break ;
			ans.pop_back();
		}
	}
}

int main(){
	int T; cin >> T;
	for(int i = 0; i<T; i++){
		int m, k;
		cin >> m >> k;
		flag = 0;
		ans.clear();
		dfs(m, k);
		if(flag){
			cout << ans.size() << "\n";
			for(int x : ans){
				cout << x << " ";
			}	cout << "\n";
		}else{
			cout << "-1\n";
		}
	}
}

Subtask 2:

As $M$ is large relative to $K$, we will employ a strategy as follows:

• First, we will let $x=2^K-1$ such that $\text{popcount}(x) = K$.
• Then, we will find an array that sums to $d = M - x$ with popcount xor equal to $0$. Notably, $d \geq 2$ as $M > 2^K > x = 2^K - 1$.
  • If $d$ is even, we can use the array $[\frac{d}{2}, \frac{d}{2}]$. This sums to $d$ and has popcount xor equal to $0$.
  • Otherwise, $d$ is odd and at least three. Ideally, we can reduce it to the even case, and it turns out, we can! We will try to make $d$ an even number by making an array with a small odd sum and popcount xor equal to $0$. For instance, we can decrease $d$ by $3$ by use the array $[1, 2]$ that has sum $3$ and popcount $0$. So our array with sum $d$ and popcount xor equal to $0$ is $[1, 2, \frac{d-3}{2}, \frac{d-3}{2}]$.

My C++ code:

#include <iostream>
#include <vector>

using namespace std;

int main(){
	int T; cin >> T;
	while(T--){
		int m, k;
		cin >> m >> k;
		int x = (1 << k) - 1;
		int d = m - x;
		vector<int> ans;	
		if(d%2 == 0){
			ans = {x, d/2, d/2};
		}else{
			ans = {x, 1, 2, (d - 3)/2, (d - 3)/2};
		}
		//for this subtask, a solution always exists!
		cout << ans.size() << "\n";
		for(int i = 0; i<ans.size(); i++){
			cout << ans[i] << " ";
		} 
		cout << "\n";
	}
}

Full solution

We now have to improve our solution for when $M$ is smaller relative to $K$. We will still use the same strategy as before of finding two arrays $a$ and $b$ where $a$ has popcount xor equal to $K$ and $b$ has popcount xor equal to $0$. From a greedy standpoint, we should aim to minimize the sum of elements in $a$ to give more leeway for constructing $b$.

For each bit $i$ on in $K$, we will add $2^{2^i} - 1$ to $a$. Notably $2^{2^i} - 1$ is the smallest integer with popcount $2^i$. For instance if $K = 5$, we would take $a = [1, 15]$ or if $K = 12$ we would take $a = [15, 255]$.

$a$ has the minimal sum of any array with popcount xor equal to $K$. We will prove this with a contradiction.

Suppose $a$ was not of the form above. Consider any element $x$ in $a$ not of the form $2^{2^i}-1$, and suppose it has popcount $c$.

• If $c$ is a power of $2$, we can just take $2^{2^c}-1$ instead of $x$. $2^{2^c}-1$ is smaller than $x$ and has the same popcount.
• Otherwise, suppose the lowest bit in $c$ is $2^j$. We can replace $x$ with $2^{2^j}-1$ and $2^{2^{c - 2^j}}-1$. As in general, $2^{s + t} - 1 > 2^{s} -1 + 2^{t} - 1$ (we use $s = j$ and $t = c - j$ here).

Our new array has the same popcount xor, but a smaller sum, thus our original $a$ could not have the minimal sum.

For instance, if our $a$ with popcount xor equal to $7$ was $[1, 63]$. We could replace $63$ (with popcount $6$) with $[2^{2^1} - 1, 2^{2^2}-1] = [3, 15]$ to get a new $a$ with a smaller sum and popcount xor equal to $7$.

Let $d = M - \sum a_i$. If $d < 0$, no such array exists, as we cannot make an array $a$ with smaller sum and popcount xor equal to $K$.

If $d \geq 2$, we can use our idea from the previous subtask.

• If $d$ is even, we have $b = [\frac{d}{2}, \frac{d}{2}]$.
• If $d$ is odd, we have $b = [1, 2, \frac{d-3}{2}, \frac{d-3}{2}]$

If $d = 0$, we can have $b$ be empty.

Finally, we just have to solve when $d = 1$. In other words, we need to increase the sum of $a$ by $1$ without changing the xor of its popcounts. This is only possible when $a$ contains $1$, and we would replace that occurrence of $1$ with a $2$. There is no other way to change the array $a$ into any other array with sum $M$ and popcount xor equal to $K$ as $a$, as defined above, has minimal sum.

Our final complexity is $O(\log K)$ per test case.

My C++ code:

#include <iostream>
#include <vector>

using namespace std;

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int T; cin >> T;
	while(T--){
		int m, k; cin >> m >> k;
		vector<int> a;
		int x = 0;
		for(int i = 0; i<5; i++){
			if(k&(1 << i)){
				a.push_back((1 << (1 << i)) - 1);
				x += a.back();
			}
		}

		int d = m - x;
		vector<int> b;
		int flag = 0; 
		if(d < 0){
			flag = 1;
		}else if(d >= 2){
			if(d%2 == 0){
				b = {d/2, d/2};
			}else{
				b = {1, 2, (d-3)/2, (d-3)/2};
			}
		}else if(d == 0){
			b = {};
		}else{
			if(a[0] == 1){
				a[0] = 2;
			}else{
				flag = -1;
			}
		}

		if(flag){
			cout << "-1\n";
		}else{
			cout << a.size() + b.size() << "\n";
			for(int i : a) 
				cout << i << " ";
			for(int i : b)
				cout << i << " " ;
			cout << "\n";
		}
	}
}