#P17729. [2026年福建省队集训]哈得慢的妖怪基米

[2026年福建省队集训]哈得慢的妖怪基米

哈得慢的妖怪基米

题目描述

恋恋正在学习集合幂级数。这一天她在一条无限长纸带上依次写下了 nn 个 [0,108][0,10^8] 内的非负整数 a1,…,ana_1,\ldots,a_n,然后在后面依次写下了所有的子集和 fS=∑i∈Saif_S=\sum_{i\in S} a_i。

突然一只哈基米从天而降,说它要哈集幂,于是把写着 a1,…,ana_1,\ldots,a_n 的这部分纸带撕碎了,并且把后面写着的子集和进行了一些修改。

恋恋忘记原来的 a1,…,ana_1,\ldots,a_n 是什么了,但是她注意到哈基米恰好修改了 tt 个子集 SS 对应的 fSf_S,并且 t<2n−2t<2^{n-2}。

现在,她给你打了个电话,请你帮她找到一组合法的 a1,…,ana_1,\ldots,a_n。

输入格式

第一行包含两个非负整数 n,tn,t。

第二行包含 2n2^n 个非负整数

f^0,f^1,…,f^2n−1,\hat f_0,\hat f_1,\ldots,\hat f_{2^n-1},

表示哈基米修改后纸带上剩下的子集和。

对于整数 0≤x<2n0\le x<2^n,假设其二进制表示为 ∑i=0n−1bi2i\sum_{i=0}^{n-1}b_i2^i,则其对应的子集为 {i+1∣bi=1}\{i+1\mid b_i=1\}。

保证存在一组 [0,108][0,10^8] 内的非负整数 a1,…,ana_1,\ldots,a_n,使得原本的子集和 fxf_x 与给定的 f^x\hat f_x 恰好在 tt 个位置不同。

输出格式

输出一行 nn 个非负整数,表示你构造出的 a1,…,ana_1,\ldots,a_n。你需要保证 ai≤108a_i\le 10^8。

如果有多组合法答案,输出任意一组即可。

输入输出样例 #1

输入 #1

3 1
0 2 5 7 7 9 100 14

输出 #1

2 5 7

说明/提示

对于样例,所有子集和依次为 0,2,5,7,7,9,12,140,2,5,7,7,9,12,14,与输入中的 0,2,5,7,7,9,100,140,2,5,7,7,9,100,14 恰好只有第 66 个位置不同。

本题采用捆绑测试。所有数据均满足 3≤n≤203\le n\le 20,0≤f^x≤2×1090\le \hat f_x\le 2\times 10^9,且保证存在一组合法的 [0,108][0,10^8] 内的 a1,…,ana_1,\ldots,a_n。对于分值不为零的子任务,还保证 t<2n−2t<2^{n-2}。

子任务编号 分值 n≤n\le t<t< 特殊性质
11 1010 2020 min⁡(2n−2,1)\min(2^{n-2},1) 无
22 min⁡(2n−2,2)\min(2^{n-2},2)
33 1515 2n−22^{n-2} A
44 2020
55 55 min⁡(2n−2,6)\min(2^{n-2},6) 无
66 1515 min⁡(2n−2,3)\min(2^{n-2},3)
77 1010 2n−22^{n-2}
88 1515
99 2020

特殊性质 A:保证存在一组合法的 a1,…,an∈{0,1}a_1,\ldots,a_n\in\{0,1\}。