Sequence Construction

题意

给定 M 和 K，要求构造一个长度 $1 \dots 100$ 的非负整数序列 a，满足：

\sum a_i = M

并且所有元素的二进制 1 的个数做异或后等于 K：

popcount(a_1) \oplus popcount(a_2) \oplus \cdots \oplus popcount(a_N) = K

如果不存在这样的序列，输出 -1。

思路

先看一个小数据暴力。它枚举 M 的所有整数拆分，并检查每个拆分的 popcount 异或值。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:13
 * update_at: 2026-07-11 18:17
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 35;

int m, k;
int path[MAXM], path_len;
int answer[MAXM], answer_len;
bool found_answer;

int popcount_int(int x) {
    int cnt = 0;
    while (x > 0) {
        if ((x & 1) != 0) {
            cnt++;
        }
        x >>= 1;
    }
    return cnt;
}

// 枚举非降的正整数拆分；0 不影响和与异或，可以不用枚举。
void dfs_partition(int min_value, int rest, int xor_value) {
    if (found_answer) {
        return;
    }
    if (rest == 0) {
        if (xor_value == k) {
            found_answer = true;
            answer_len = path_len;
            for (int i = 1; i <= path_len; i++) {
                answer[i] = path[i];
            }
        }
        return;
    }

    for (int x = min_value; x <= rest; x++) {
        path_len++;
        path[path_len] = x;
        dfs_partition(x, rest - x, xor_value ^ popcount_int(x));
        path_len--;
        if (found_answer) {
            return;
        }
    }
}

void solve_one_case() {
    cin >> m >> k;

    path_len = 0;
    answer_len = 0;
    found_answer = false;
    dfs_partition(1, m, 0);

    if (!found_answer) {
        cout << -1 << '\n';
        return;
    }

    cout << answer_len << '\n';
    for (int i = 1; i <= answer_len; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << answer[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_one_case();
    }

    return 0;
}

暴力可以帮助我们确认小数据是否有解，但满分中 M 可达 $10^9$ ，不能枚举拆分。

关键是先构造一个“骨架数组” a，让它的 popcount 异或已经等于 K，并且总和尽量小。这样剩下的和就更容易补上。

如果 K 的第 i 个二进制位是 1，我们放入：

2^{2^i} - 1

这个数的二进制全是 1，并且恰好有 $2^i$ 个 1，所以它的 popcount 是 $2^i$ 。

例如：

`K` 中的位	放入的数	这个数的 `popcount`
$2^0$	$1$	$1$
$2^1$	$3$	$2$
$2^2$	$15$	$4$
$2^3$	$255$	$8$
$2^4$	$65535$	$16$

把这些 popcount 异或起来，正好得到 K。

为什么这是最小骨架？因为想要一个数的 popcount 为 c，最小的数就是二进制低 c 位全为 1 的数，也就是 $2^c-1$ 。如果某个 popcount 不是 2 的幂，还可以拆成若干个 2 的幂，拆开后的总和更小。因此按照 K 的二进制位拆，是总和最小的构造。

设骨架总和为 base，剩余：

rest = M - base

分情况讨论：

rest < 0：骨架已经超过 M，无解。
$rest = 0$ ：直接输出骨架。
$rest >= 2$ 且为偶数：加入 $rest/2, rest/2$ ，两个数的 popcount 相同，异或为 0。
$rest >= 3$ 且为奇数：加入 $1, 2, (rest-3)/2, (rest-3)/2$ 。其中 $popcount(1) = popcount(2) = 1$ ，后两个数也相同，整体异或为 0。
$rest = 1$ ：只能尝试把骨架里的 1 改成 2。它们的 popcount 都是 1，总和增加 1 且异或不变。如果骨架里没有 1，无解。

这样补进去的数对 popcount 异或没有影响，只负责把总和补到 M。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:13
 * update_at: 2026-07-11 18:17
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> ans;

void solve_one_case() {
    ll m;
    int k;
    cin >> m >> k;

    ans.clear();
    ll base_sum = 0;

    // K 的第 i 位为 1，就放入一个 popcount 为 2^i 的最小数。
    for (int i = 0; i <= 4; i++) {
        if ((k & (1 << i)) != 0) {
            ll value = (1LL << (1 << i)) - 1;
            ans.push_back(value);
            base_sum += value;
        }
    }

    ll rest = m - base_sum;
    if (rest < 0) {
        cout << -1 << '\n';
        return;
    }

    if (rest == 1) {
        // 只有包含 1 时，才能把 1 改成 2，sum +1 且 popcount 不变。
        bool changed = false;
        for (int i = 0; i < (int)ans.size(); i++) {
            if (ans[i] == 1) {
                ans[i] = 2;
                changed = true;
                break;
            }
        }
        if (!changed) {
            cout << -1 << '\n';
            return;
        }
    } else if (rest >= 2) {
        if (rest % 2 == 0) {
            ans.push_back(rest / 2);
            ans.push_back(rest / 2);
        } else {
            ans.push_back(1);
            ans.push_back(2);
            ans.push_back((rest - 3) / 2);
            ans.push_back((rest - 3) / 2);
        }
    }

    cout << ans.size() << '\n';
    for (int i = 0; i < (int)ans.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_one_case();
    }

    return 0;
}

复杂度

K \leqslant 31，最多只有 5 个二进制位需要处理。

每组数据时间复杂度为 $O(\log K)$ ，构造出的序列长度不超过 9，空间复杂度为 $O(1)$ 。

总结

本题的核心是先最小化“让 popcount 异或等于 K”所需的总和。

剩余部分只要构造出 popcount 异或为 0 的若干数即可。相同的两个数异或贡献为 0，这是补齐总和的主要工具。

目录

题意

思路

代码

复杂度

总结