礼物
题目背景
由于你出色的完成了前面两道题目,善良的 __stdcall 决定给你一个小礼物,给拼搏在 AK 这套题之路上的你,一个有力的援助。
题目描述
__stdcall 决定给你 $n$ 个礼物,每个礼物有一个魔力值 $a_i$。
这些礼物的魔力值都是独一无二的,两两互不相同。这些礼物都有着神奇的魔力,如果两个礼物 $i, j$ 的魔力值满足 $a_i \operatorname{bitand} a_j \ge \min(a_i, a_j)$,那么这两个礼物的魔力将会相互抵消,因此它们不能放在一个箱子里。
这里的 $\operatorname{bitand}$ 表示按位与运算,如果你对这一运算不够了解,请参考:<https://baike.baidu.com/item/%E6%8C%89%E4%BD%8D%E4%B8%8E/9601818>。
作为发礼物苦力的 ljt12138 的箱子并不多,不过幸运的是,每个箱子都足够大。现在他请求你帮助他合理分配,用**尽可能少**的箱子装下所有礼物。换言之,使得每个礼物都被恰好装入一个箱子中,且同一个箱子中的礼物魔力不会相互抵消。如果有多种合法的方案,你只需要给出**任意一种**。
ljt12138 十分善良,如果你只能求出所需要的箱子数,也可以获得该测试点 $60\%$ 的分数,关于这一点,请参考下面的提示与说明。
输入输出格式
输入格式
- 第一行两个数 $n$ 和 $k$,$n$ 为礼物总数,$k$ 为一个参数,方便你进行计算。
- 第二行 $n$ 个两两不同的数$a_i$,满足 $0\le a_i < 2^k$,表示礼物的魔力值。
输出格式
- 第一行输出一个数。如果你不希望输出方案,请输出0;如果你希望输出方案,请输出 $1$。**如果你在这一行输出了不符合要求的信息,将被判为 WA**。
- 第二行一个数 $m$,表示你将礼物装到了 $m$ 个箱子里。
- 如果你在第一行输出了 $1$,接下来 $m$ 行,每行表示一个箱子:首先一个数 $s_i$,表示当前箱子中礼物的个数;接下来 $s_i$ 个数,表示当前子集。
输入输出样例
输入样例 #1
5 3
0 4 7 1 6
输出样例 #1
1
4
1 0
2 1 4
1 6
1 7
说明
### 附加样例
你可以在 <https://pan.baidu.com/s/1A8_ZA4yXXi5y6771x9JKUw> 下载附加样例。
### 关于输出方案
- 如果你在第一行输出了 $0$,而正确回答了最小所需的箱子数,将获得测试点 $60\%$ 的分数。
- 如果你在第一行输出了 $1$,正确回答了最小所需的箱子数,但没有给出正确的方案,也将获得该测试点 $60\%$ 的分数。
- 如果你没有正确回答最小所需的箱子数,将不会获得该测试点的分数。
- 请选手注意,如果你未按照上述格式输出答案,将无法获得任何分数。
数据 $n, k$ 的关系由下面的表格给出:
|数据编号| $n$ | $k$ |
|:----:|:----:|:----:|
|$1$|$5$|$3$|
|$2$|$6$|$3$|
|$3$|$7$|$10$|
|$4$|$8$|$10$|
|$5$|$16$|$7$|
|$6$|$17$|$8$|
|$7$|$17$|$9$|
|$8$|$17$|$20$|
|$9$|$2\times 10^3$|$17$|
|$10$|$2.5\times 10^3$|$18$|
|$11$|$3\times 10^3$|$19$|
|$12$|$3\times 10^3$|$20$|
|$13$|$2.5\times 10^4$|$15$|
|$14$|$2.5\times 10^4$|$15$|
|$15$|$5\times 10^4$|$16$|
|$16$|$5\times 10^4$|$16$|
|$17$|$2.5\times 10^5$|$18$|
|$18$|$5\times 10^5$|$19$|
|$19$|$10^6$|$20$|
|$20$|$10^6$|$20$|