[AGC012C] Tautonym Puzzle

题意翻译

我们称一个字符串 $x$ 是好的当且仅当它满足以下条件: - $x$ 可以被表示为另外一个串 $y$ 复制一遍得到,即 $x=\overline {yy}$。 举个例子:`aa` 和 `bubobubo` 是好的,`a`、`abcabcabc` 和 `abba` 不是。 现在要求一个串 $s$ 满足下列条件,可以证明这个串存在: - $|s|\leqslant 200$ - 字符集大小为 $100$,每个字符用 $[1,100]$ 的整数表示。 - 在 $s$ 的所有的 $2^{|s|}$ 个子序列中,恰好有 $N$($1 \le N \le 10 ^ {12}$)个串是好的,其中 $N$ 是给出的。

题目描述

[problemUrl]: https://atcoder.jp/contests/agc012/tasks/agc012_c 文字列 $ x $ が以下の条件を満たすとき、$ x $ を *良い文字列* と呼びます。 - 条件:$ x $ はある長さ $ 1 $ 以上の文字列 $ y $ を $ 2 $ 回繰り返した文字列 $ yy $ で表すことができる。 例えば `aa`,`bubobubo` などは良い文字列ですが、空文字列、`a`,`abcabcabc`,`abba` などは良い文字列ではありません。 ワシとフクロウが良い文字列に関するパズルを作りました。 以下の条件を満たす文字列 $ s $ をどれか $ 1 $ つ求めてください。この問題の制約下で、そのような文字列が必ず存在することが証明できます。 - $ 1\ ≦\ |s|\ ≦\ 200 $ - $ s $ は $ 1 $ から $ 100 $ までの整数で表される $ 100 $ 種類の文字のみからなる。 - $ s $ の $ 2^{|s|} $ 個ある部分列のうち、良い文字列であるようなものは $ N $ 個ある。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $

输出格式


$ 1 $ 行目には $ s $ の長さ $ |s| $ を出力せよ。 $ 2 $ 行目に $ s $ の各要素を $ 1 $ 文字目から順に空白区切りで出力せよ。$ s $ が上記の条件を満たすならば正解となる。

输入输出样例

输入样例 #1

7

输出样例 #1

4
1 1 1 1

输入样例 #2

299

输出样例 #2

23
32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10

说明

### 制約 - $ 1\ ≦\ N\ ≦\ 10^{12} $ ### Sample Explanation 1 $ s $ の部分列であって良い文字列となるようなものは (1,1) と (1,1,1,1) の $ 2 $ 種類があります。(1,1) であるような部分列は $ 6 $ 個、(1,1,1,1) であるような部分列は $ 1 $ 個あるため、合計 $ 7 $ 個です。