1. 题目

传送门=￣ω￣=

题目描述

我们称一个字符串 $x$是好的，当且仅当它满足下列条件：
条件：$x$可以被表示为连续两个相同的非空串 $y$首尾相连
例如，’aa’ 和’bubobubo’ 是好的；但是空串，’a’，’abcabcabc‘和’abba’ 都不是好的。
Eagle 和 Owl 提出了关于好串的问题。请找出一个串 s 使得其满足下述条件：
1. $1≤|s|≤200$
2. $s$的每一个字符都是 $1$到 $100$之间的整数
3. $s$的 $2^{|s|}$个子串中，有恰好 $N$个是好串

输入格式

一个整数 $N$。

输出格式

第一行，一个整数表示 $s$的长度。

第二行，用空格隔开的若干个整数，描述字符串 $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}$

2. 题解

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

首先可以想到对于 $n=1$的询问答案是 $1, 1$

设 $f(s)$表示字符串 $s$的 “好” 子串个数。

然后可以构造出如下性质：

（其中 $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$：

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

然后就能倍增了是吧。。。

这样构造出来的结果长度为 $O(log _ 2 n)$，复杂度也是 $O(log _ 2 n)$的，真美妙=￣ω￣=

代码：

#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;
}