https://emtubasa.hateblo.jp/entry/2019/08/27/144125

解法

$dp1[i][j] = i$ 番目に $j$ を置くような数列の場合の数(ただし、 $j \leqq \sqrt{N}$ )
$dp2[i][j] = i$ 番目に、 $xj \leqq N \lt x(j+1)$ を満たすような $x( x \gt \sqrt{N})$ を置く数列の場合の数
とします。
$\sqrt{N}$ 以下で最大の整数を $p$ 、 $xj \leqq N \lt x(j+1)$ を満たすような $x( x \gt \sqrt{N})$ の個数を $c_{j}$ とすると、それぞれ次のように遷移を行うことができます。
$\displaystyle dp1[i + 1][j] = \sum_{s = 1}^{p} dp1[i][s] + \sum_{m = j}^{p}dp2[i][m]$
$\displaystyle dp2[i+1][j] = \sum_{s = 1}^{j}dp1[i][s] \times c_{j}$

あとは、全てΣの形になっているので、この部分を累積和で高速化することにより、 $dp1[k][j],dp[k][j]$ の総和が答えとなります。
初期値は $dp1[0][1] = 1$ 、それ以外が $0$ です。