#6813. [SeqOI 21W] Cesenque

内存限制:512 MiB 时间限制:1000 ms 输入文件:cesenque.in 输出文件:cesenque.out
题目类型:传统 评测方式:无测试数据
上传者: Ericnth

题目描述

Rolling_Code 想要把一个集合 S=\{a_1,a_2\dots a_n\} 变成一个序列。

但是她发现一个集合只能组成长度为 1 的序列。

于是 Rolling_Code 把这个集合的所有子集也想要加入到这个序列中。

但是 Rolling_Code 喜欢守序,因此她希望相邻两个集合的 对称差 的大小必须恰为 k

两个集合 A,B 的对称差 A\ \Delta\ B 定义如下:

A\ \Delta\ B=(A\cup B)\setminus(A\cap B)

也即 A\ \Delta\ B=\{x|x\in A\ \operatorname{or}\ x\in B\ \operatorname{and}\ x\notin{A\cup B}\}

现在请你告诉 Rolling_Code 能不能完成这个目标,同时也请告诉她一种合法的序列,因为 Rolling_Code 太笨了,自己试了好长时间都没有试出来。

输入格式

输入集合大小 n 和限制 k

输出格式

第一行输出一个整数 0 或者 1,其中 0 代表不存在这样的序列,而 1 代表存在这样的序列。

接下来一行,如果第一行输出的是 1 的话,输出任何一种合法序列即可。

特别的,为了输出方便,请二进制压缩过后输出,详细的输出方法如下:

设一个二进制数有第 0 到第 n-1 位,从低到高第 i 位为 1 代表 a_{i+1} 在这个子集中被选中,否则代表没有被选中。

请用 10 进制输出这个二进制数,没有前导 0

样例

Input1
4 3
Output1
1
0 14 3 13 6 8 5 11 12 2 15 1 10 4 9 7

数据范围与提示

对于 100\% 的数据,满足 1\le k\le n\le 20

本题采用 Special Judge,子任务评测

子任务编号 n k 子任务总分 依赖子任务
0 \le 4 5
1 \le 8 25 Subtask 0
2 =1 10
3 =n-1 15
4 45 Subtask 0~3