# 1. 题目

#### 题目描述

Eagle 和 Owl 提出了关于好串的问题。请找出一个串 s 使得其满足下述条件：
1. $1≤|s|≤200$
2. $s$的每一个字符都是 $1$到 $100$之间的整数
3. $s$的 $2^{|s|}$个子串中，有恰好 $N$个是好串

#### 样例输入 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}$

# 2. 题解

QAQ 初赛考完了来道构造题压压惊.jpg

（其中 $c$为一个 $X, Y$内都未出现过的字符，$X,Y$分别是两个字符串）

$f(c + X + Y + c) = f(X + Y) + 1$
$f(c + X + c + Y) = 2 \times f(X + Y) + 1$

（备注一下第二个性质的 $+1$是因为 $c$除了和 $X,Y$组合还能组成一个 $c, c$，即 $X,Y$都选择空串）

• $x$为奇数：转化为询问 $\frac {x – 1} 2$（即第二条性质）
• $x$为偶数：转化为询问 $x – 1$（即第一条性质），然后询问就成了奇数

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n, num;

list<int> L, R;

void Work(LL a)
{
if (!a) return;
if (a & 1) Work(a >> 1), L.push_front(++num), R.push_front(num);
else Work(a - 1), L.push_front(++num), R.push_back(num);
}

int main(int argc, char const* argv[])
{
scanf("%lld", &n), Work(n);
printf("%lu\n", L.size() + R.size());
for (list<int>::iterator i = L.begin(); i != L.end(); i++) printf("%d ", *i);
for (list<int>::iterator i = R.begin(); i != R.end(); i++) printf("%d ", *i);
putchar(10);
return 0;
}
{"ft_lang_label":"__label__zh","ft_lang_prob":0.6376083,"math_prob":0.9999839,"size":1452,"snap":"2022-40-2023-06","text_gpt3_token_len":905,"char_repetition_ratio":0.0711326,"word_repetition_ratio":0.008583691,"special_character_ratio":0.46969697,"punctuation_ratio":0.16253443,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99934125,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-02-01T08:41:07Z\",\"WARC-Record-ID\":\"<urn:uuid:8ed7930f-50e0-4bc6-9414-d8757e69d9f7>\",\"Content-Length\":\"60856\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a1191d5d-6138-4c0b-bcf5-355f72c3f890>\",\"WARC-Concurrent-To\":\"<urn:uuid:39c3aeb0-461c-4d36-b7b0-8488120346fa>\",\"WARC-IP-Address\":\"154.17.1.77\",\"WARC-Target-URI\":\"https://www.mina.moe/archives/9637\",\"WARC-Payload-Digest\":\"sha1:SMNFHHTRAOAINTVV45ZV6TZPSU2RIQ2P\",\"WARC-Block-Digest\":\"sha1:D4GYX3M2PNBLWWJSFKOE7HXREXKFREMA\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-06/CC-MAIN-2023-06_segments_1674764499919.70_warc_CC-MAIN-20230201081311-20230201111311-00843.warc.gz\"}"}