哈得慢的妖怪基米
题目描述
恋恋正在学习集合幂级数。这一天她在一条无限长纸带上依次写下了 n 个 [0,108] 内的非负整数 a1,…,an,然后在后面依次写下了所有的子集和 fS=∑i∈Sai。
突然一只哈基米从天而降,说它要哈集幂,于是把写着 a1,…,an 的这部分纸带撕碎了,并且把后面写着的子集和进行了一些修改。
恋恋忘记原来的 a1,…,an 是什么了,但是她注意到哈基米恰好修改了 t 个子集 S 对应的 fS,并且 t<2n−2。
现在,她给你打了个电话,请你帮她找到一组合法的 a1,…,an。
输入格式
第一行包含两个非负整数 n,t。
第二行包含 2n 个非负整数
f^0,f^1,…,f^2n−1,
表示哈基米修改后纸带上剩下的子集和。
对于整数 0≤x<2n,假设其二进制表示为 ∑i=0n−1bi2i,则其对应的子集为 {i+1∣bi=1}。
保证存在一组 [0,108] 内的非负整数 a1,…,an,使得原本的子集和 fx 与给定的 f^x 恰好在 t 个位置不同。
输出格式
输出一行 n 个非负整数,表示你构造出的 a1,…,an。你需要保证 ai≤108。
如果有多组合法答案,输出任意一组即可。
输入输出样例 #1
输入 #1
3 1
0 2 5 7 7 9 100 14
输出 #1
2 5 7
说明/提示
对于样例,所有子集和依次为 0,2,5,7,7,9,12,14,与输入中的 0,2,5,7,7,9,100,14 恰好只有第 6 个位置不同。
本题采用捆绑测试。所有数据均满足 3≤n≤20,0≤f^x≤2×109,且保证存在一组合法的 [0,108] 内的 a1,…,an。对于分值不为零的子任务,还保证 t<2n−2。
| 子任务编号 |
分值 |
n≤ |
t< |
特殊性质 |
| 1 |
10 |
20 |
min(2n−2,1) |
无 |
| 2 |
min(2n−2,2) |
| 3 |
15 |
2n−2 |
A |
| 4 |
20 |
| 5 |
5 |
min(2n−2,6) |
无 |
| 6 |
15 |
min(2n−2,3) |
| 7 |
10 |
2n−2 |
| 8 |
15 |
| 9 |
20 |
特殊性质 A:保证存在一组合法的 a1,…,an∈{0,1}。