题解

思路

设 $dp[x]$ 表示当前长度下、末项为 $x$ 的好序列数量。若下一项为 $y$，合法条件正是 $x\mid y$。直接枚举所有 $(x,y)$ 需要二次复杂度，但固定 $x$ 后，合法的 $y$ 恰好是 $x,2x,3x,\ldots$。

做法

长度为 $1$ 时，每个 $1\le x\le n$ 都有一个序列，所以全部状态初始化为 $1$。随后重复 $k-1$ 层：枚举旧末项 $x$，再枚举不超过 $n$ 的所有 $x$ 的倍数 $y$，把 $dp[x]$ 加入新状态 $ndp[y]$。每次加法都对 $10^9+7$ 取模。最后对全部末项状态求和。

一层转移次数为 $\sum_{x=1}^n\lfloor n/x\rfloor=O(n\log n)$。

正确性证明

长度为 $1$ 的初始化显然逐一表示全部合法序列。假设 $dp[x]$ 正确统计了长度为 $r$ 且末项为 $x$ 的好序列。算法只把它转移到 $x$ 的倍数 $y$，所以新相邻项满足整除条件；反之，任何长度为 $r+1$、末项为 $y$ 的好序列，删去末项后有唯一前驱末项 $x$ 且 $x\mid y$，会由算法恰好加入一次。因此新状态正确。归纳到长度 $k$ 后，对末项求和即得到全部好序列数。

复杂度分析

时间复杂度为 $O(kn\log n)$，空间复杂度为 $O(n)$。

子任务说明

• $n,k\le8$ 时递归枚举全部候选序列。
• $n,k\le300$ 时枚举所有前驱与后继，做 $O(kn^2)$ 动态规划。
• 满数据只枚举每个状态的倍数，利用调和级数优化。