[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 $ 個です。