我们需要构造一个严格递增的正整数序列 a1<a2<⋯<an,满足所有数的按位或(共鸣融合)结果恰好等于给定的目标值 k。
算法的核心思想是:利用 k 的二进制表示中所有为 1 的位,枚举这些位的所有非空子集,每个子集对应的数值就是选中位的权重之和。这些数值具有以下性质:
在古老符文魔法中,魔法师需要编织一条由 n 枚符文组成的魔力链。每枚符文具有一个正整数魔力值,且后一枚的魔力必须严格大于前一枚。此外,整条链的“共鸣融合”魔力必须恰好等于给定的目标值 k。
共鸣融合的规则定义如下:对于两个非负整数,将它们按照二进制位进行逐位逻辑或运算,记作 ⊕。对于序列 a1,a2,…,an,其共鸣融合结果为 a1⊕a2⊕⋯⊕an。
现在给定链的长度 n 和目标值 k,请你构造一个魔力值序列 a1,a2,…,an 满足:
如果存在这样的序列,请输出任意一组解;否则指出不存在。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册