2379. s01串
1000ms
256MB
简单
字符串
题目描述
已知一个只包含字符 `'0'` 和 `'1'` 的字符串 $s$，初始状态为 `"0"`。
该字符串将按照以下规则进行变换：
- 字符 `'0'` 变换为 `"1"`。
- 字符 `'1'` 变换为 `"01"`。
请编写程序，计算并输出经过 $n$ 次变换后所得到的字符串。
输入格式
- 输入一个整数 $n$ ($0 \le n \le 19$)，表示变换的次数。
输出格式
- 输出一行字符串，表示经过 $n$ 次变换后的字符串。
样例 1
输入 (Input)
3
输出 (Output)
101
样例说明
- **样例说明**：
- 初始状态（第 0 次变换后）：`"0"`
- 第 1 次变换：`"0"` 中的 `'0'` 变为 `"1"` $\rightarrow$ `"1"`
- 第 2 次变换：`"1"` 中的 `'1'` 变为 `"01"` $\rightarrow$ `"01"`
- 第 3 次变换：`"01"` 中的 `'0'` 变 `"1"`，`'1'` 变 `"01"` $\rightarrow$ `"101"`
- 对于 $100\%$ 的数据：$0 \le n \le 19$。
- **算法提示**：
观察变换过程，设第 $i$ 次变换后的字符串为 $S_i$：
- $S_0 = \text{"0"}$
- $S_1 = \text{"1"}$
- $S_2 = \text{"01"}$
- $S_3 = \text{"101"}$
- $S_4 = \text{"01101"}$
容易发现，自 $n \ge 2$ 起，变换后的字符串满足以下递推关系：
$$S_n = S_{n-2} + S_{n-1}$$
其中 $+$ 表示字符串拼接。由于 $n$ 的最大值为 19，最终的字符串长度仅为 $F_{19} = 6765$ 字符，可以直接使用 `std::string` 进行递推拼接，也可以通过直接模拟字符替换来解决。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功