11294799 小淘的完美序列

题目链接: https://www.nowcoder.com/practice/7c391af0215a4a7595eb3dd3d9b7f107

支持语言: C++, Java

---

题意

给定正整数 $n$ 和 $m$ ，构造一个长度为 $n$ 的完美序列：序列中每个元素均为 $m$ 的非零子掩码（即每个元素 $a_i$ 满足 $a_i\ \&\ m = a_i$ 且 $a_i \geq 1$ ），所有元素互不相同，且所有元素按升序排列，全部元素按位或等于 $m$ 。

若无法构造则输出 NO，否则输出 YES 及序列。

---

分析

可行性判断

$m$ 的非零子掩码数量恰好为 $2^k - 1$ ，其中 $k = \text{popcount}(m)$ （ $m$ 的二进制中 $1$ 的个数）。

若 $n > 2^k - 1$ ：不可能找到 $n$ 个不同的正子掩码，输出 NO。
否则：输出 YES。

构造方法

输出 $m$ 的第 $1, 2, \ldots, n-1$ 小正子掩码，最后一个元素输出 $m$ 本身。

这样构造保证：

所有元素均为 $m$ 的正子掩码。
全部元素按位或 $= m$ （因为最后一个元素就是 $m$ ）。
所有元素互不相同（前 $n-1$ 个下标互不相同， $m$ 是最大子掩码不在前 $n-1$ 中，因为 $n-1 < 2^k - 1$ ）。
序列升序（见下方证明）。

高效生成第 $j$ 小子掩码

设 $m$ 的二进制中 $1$ 所在位置（从低到高）依次为 $p_0 < p_1 < \cdots < p_{k-1}$ ，对应的位值为 $b_i = 2^{p_i}$ 。

则 $m$ 的第 $j$ 小正子掩码（ $1 \le j \le 2^k - 1$ ）可由以下方法得到：

将 $j$ 写成二进制，若 $j$ 的第 $i$ 位（从低位数）为 $1$ ，则贡献 $b_i$ ：

$ $\text{spread}(j) = \sum_{i : \text{bit}_i(j) = 1} b_i$ $

验证：以 $m = 7$ （位值 $b_0=1, b_1=2, b_2=4$ ）为例：

$j$	二进制	$\text{spread}(j)$
1	001	1
2	010	2
3	011	3
4	100	4
5	101	5
6	110	6
7	111	7

映射保序性证明

对任意 $j < j'$ ，有 $\text{spread}(j) < \text{spread}(j')$ 。

设 $j$ 与 $j'$ 最高不同位为第 $b$ 位。由于 $j < j'$ ， $j'$ 的第 $b$ 位为 $1$ ，贡献 $b_b = 2^{p_b}$ 。而 $j$ 在第 $b$ 位以下各位的贡献之和满足：

$ $\sum_{i < b} b_i = \sum_{i < b} 2^{p_i} \leq 2^{p_b - 1} + 2^{p_b - 2} + \cdots + 1 = 2^{p_b} - 1 < b_b$ $

（因为 $p_0 < p_1 < \cdots < p_{b-1} < p_b$ ，最坏情况下 $p_i = p_b - (b-i)$ ，总和 $< 2^{p_b}$ 。）

因此 $\text{spread}$ 映射是严格单调递增的，直接按 $j = 1, 2, \ldots, n-1$ 输出即为升序序列。

时间复杂度: $O(n \cdot k)$ ，其中 $k \leq 44$ 。

---

代码

C++

#include <bits/stdc++.h>
using namespace std;

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

    long long n, m;
    cin >> n >> m;

    vector<long long> bits;
    for (int i = 0; i < 44; i++) {
        if (m & (1LL << i)) {
            bits.push_back(1LL << i);
        }
    }

    int k = bits.size();
    long long total_submasks = (k >= 40) ? (long long)9e18 : (1LL << k) - 1;

    if (n > total_submasks) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";

    auto jth_submask = [&](long long j) -> long long {
        long long val = 0;
        int idx = 0;
        while (j > 0) {
            if (j & 1) val |= bits[idx];
            j >>= 1;
            idx++;
        }
        return val;
    };

    for (long long j = 1; j <= n - 1; j++) {
        cout << jth_submask(j) << ' ';
    }
    cout << m << '\n';

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());

        long[] bits = new long[44];
        int k = 0;
        for (int i = 0; i < 44; i++) {
            if ((m & (1L << i)) != 0) {
                bits[k++] = 1L << i;
            }
        }

        long totalSubmasks = (k >= 40) ? Long.MAX_VALUE : (1L << k) - 1;

        if (n > totalSubmasks) {
            System.out.println("NO");
            return;
        }

        StringBuilder sb = new StringBuilder();
        sb.append("YES\n");

        for (long j = 1; j <= n - 1; j++) {
            sb.append(jthSubmask(j, bits));
            sb.append(' ');
            if (j % 100000 == 0) {
                System.out.print(sb);
                sb.setLength(0);
            }
        }
        sb.append(m).append('\n');
        System.out.print(sb);
    }

    static long jthSubmask(long j, long[] bits) {
        long val = 0;
        int idx = 0;
        while (j > 0) {
            if ((j & 1) != 0) val |= bits[idx];
            j >>= 1;
            idx++;
        }
        return val;
    }
}

---

关键点

可行性: 非零子掩码数量 $= 2^k - 1$ ， $n$ 不超过此值则有解。
构造: 前 $n-1$ 个元素取最小的 $n-1$ 个子掩码，最后输出 $m$ ，保证覆盖所有位。
枚举: 第 $j$ 小子掩码 $=$ 将 $j$ 的二进制位"展开"到 $m$ 的各位位置， $O(k)$ 时间直接计算，无需排序或优先队列。
单调性: 展开映射严格保序，故输出天然有序。