给出自然数 � n，要求按如下方式构造数列： 只有一个数字 � n 的数列是一个合法的数列。 在一个合法的数列的末尾加入一个自然数，但是这个自然数不能超过该数列最后一项的一半，可以得到一个新的合法数列。 请你求出，一共有多少个合法的数列。两个合法数列 � , � a,b 不同当且仅当两数列长度不同或存在一个正整数 � ≤ ∣ � ∣ i≤∣a∣，使得 � � ≠ � � a i ​  =b i ​ 。

这个题目可以使用动态规划来解决。

设 $f_i$ 表示以 $i$ 为结尾的合法数列的个数，那么 $f_i$ 可以由 $f_{i/2}, f_{i/2-1}, \cdots, f_1$ 转移而来。

具体地，当 $j \in [1, i/2]$ 时，若 $i$ 可以接在以 $j$ 为结尾的合法数列后面，则 $f_i$ 可以加上 $f_j$。

最终答案即为 $\sum_{i=1}^n f_i$。

根据上述转移方程，我们可以使用状态压缩 DP 来解决这个问题。时间复杂度为 $O(n^2)$。

以下是Python代码实现：

n = int(input())

f = [0] * (n + 1)
f[1] = 1

for i in range(2, n + 1):
    for j in range(1, i // 2 + 1):
        if i % j == 0 and j <= i // 2:
            f[i] += f[j]
print(sum(f))

以上代码中，我们先读入自然数 $n$，然后初始化 $f_1=1$。接着，我们从 $2$ 开始循环，对于每个 $i$，我们枚举 $j$，若 $i$ 可以接在以 $j$ 为结尾的合法数列后面，则将 $f_i$ 加上 $f_j$。最终，我们输出 $\sum_{i=1}^n f_i$ 即可得到答案。