Codeforces 414B Mashmokh and ACM：DP 計數好序列

問題描述

長度為 k 的非遞減序列 b₁≤b₂≤...≤bₖ≤n，滿足 bᵢ 整除 bᵢ₊₁。求方案數模 1e9+7。

DP 狀態定義

dp[i][j]：以數字 i 結尾、長度為 j 的好序列個數

轉移方程

dp[i][j] = Σ dp[d][j-1] (d 整除 i)

初始：dp[i][1] = 1

答案：Σ dp[i][k]

優化實現