#P6608. [Code+#7] 神秘序列

[Code+#7] 神秘序列

题目描述

E.Space 做了一个梦。

他梦到了一个神秘的序列,有人告诉他,这个序列和明天的考试有一些密切的关联。

他决心要把这个序列记住。可醒来之后,E.Space 发现自己没有记住这个序列,甚至连序列的长度都不记得了。不过,他记得这个序列有一个神奇的性质。

在梦中,E.Space 对它进行了一系列的操作。记这个序列为 a1,a2,,ana_1, a_2, \dots, a_n,开始时它满足 1in,ai0\forall 1\le i\le n, a_i \ge 0,并且 an0a_n \neq 0

之后,E.Space 在每次操作时选择一个满足 ai=ia_i=iii,将 aia_i 变为 00,并且将 a1,a2,,ai1a_1, a_2, \dots, a_{i-1} 分别变为原来的值加 11

E.Space 记得,在 n+kn+k 次操作之后,这个序列变成了全 00 序列,即 a1=a2==an=0a_1=a_2=\cdots =a_n= 0

E.Space 知道可能有多个序列满足这个性质,但是他还是希望你告诉他一种可能的情况,因为,说不定所有满足这个性质的序列都可以在考试时派上用场呢。

他的考试成绩就交给你了。

输入格式

输入一行一个正整数 kk

输出格式

如果你找到了满足 E.Space 描述的性质的序列,那么输出两行。

第一行一个正整数 nn

第二行 nn 个非负整数,a1,a2,,ana_1, a_2, \dots, a_n,其中 a0a\neq 0,表示这个神秘序列。

如果存在多种可能的神秘序列,只需输出任意一种。如果不存在这样的神秘序列,输出一行 Daydream! 来告诉 E.Space 他在做白日梦。

1
2
1 2
5
4
1 2 2 4

提示

子任务 111010 分):k6k\le 6

子任务 222525 分):k106k\le 10^6

子任务 333030 分):k1011k\le 10^{11},如果有解则保证存在一个解满足 1i<n,aii\forall 1\le i< n, a_i \neq i

子任务 442828 分):k1011k\le 10^{11}

子任务 5577 分):k1012k\le 10^{12}