考虑 DP。

状态

令 $f[\ell][x]$ 表示长度为 $\ell$，首项不超过 $x$ 的序列的个数。
答案是 $f[K][N]$。
有递推 $f[\ell][x] = f[\ell][x - 1] + f[\ell - 1][\floor{N/x}]$。照这个递推式求解，复杂度度太高；把它改成
$f[\ell][x] = \sum_{y = 1}^{x} f[\ell - 1][\floor{N/y}]$ 也就是枚举首项。
我们的目标是求出 $f[K][N]$，结合递推式来看，可以发现我们需要计算的状态的第二维都可以写成 $\floor{N/i}$。而我们熟知 $\floor{N/i}$ 的不同取值不超过 $2 \sqrt{N}$ 个。因此需要计算的状态不超过 $2K\sqrt{N}$ 个。

先来解决状态表示的问题，也就是 $\floor{N/i}$ 的表示问题。虽然 $\floor{N/i}$ 的取值不超过 $2\sqrt{N}$ 个，但是不能直接以 $\floor{N/i}$ 作为数组下标。可以这样做，对于 $\color{blue}{ i \le \sqrt{N} }$，用 $i$ 表示 $\floor{N/i}$，对于 $\color{red}{ i \ge \sqrt{N} }$，直接以 $\floor{N/i}$ 作为下标。从代码实现的角度说就是开两个数组，$f_1[1..K][1..\floor{\sqrt N}],\ f_2[1..K][1..\floor{\sqrt N}]$，$f_1[\ell][i] := f[\ell][i]$，$f_2[\ell][i] := f[\ell][\floor{N/i}]$。

注①：当 $N$ 是完全平方数时，$i \le \sqrt N$ 与 $i \ge \sqrt N$ 这两段中都含有 $\sqrt{N}$，这并不会造成问题。实际上分段时两侧都取等号是有意为之，这样可以使得递推式更简洁并且没有 corner case。这种分段方法适用于许多跟 $\floor{N/i}$ 相关的分块问题。

注②：关于上一段所说的“对于 $i \le \sqrt N$，用 $i$ 表示 $\floor{N/i}$”，我们不需要关心 $i \mapsto \floor{N/i}$ 是不是单射。这里所谓“表示 $\floor{N/i}$”是说设计一种方法来把所有需要计算的 $f[\ell][\floor{N/i}]$ 紧凑地存到数组里并且可以快速地由 $\ell, i$ 这两个 key 查到 $f[\ell][\floor{N/i}]$ 的值。不过可以证明，对于 $i \le \sqrt{N}$，$i \mapsto \floor{N/i}$ 确实是单射。

递推

对于 $f_1$，有递推
$f_1[l][x] = f_1[l][x - 1] + f[l - 1][\floor{N/x}]$
由于 $1 \le x \le \floor{\sqrt{N}}$，有 $f[l - 1][\floor{N/x}] = f_2[l-1][x]$，从而有
$f_1[l][x] = f_1[l][x - 1] + f_2[l-1][x]$

对于 $f_2$，有递推式
$f_2[l][i] = f_2[l][i+1] + \sum_{x=\floor{N/(i+1)} + 1}^{\floor{N/i}} f[l -1][\floor{N/x}] $
容易证明下列几个不等式

1. $\floor{N/i} \ge \floor{N/(i + 1)}$
2. $\floor{N/\floor{N/i}} \ge i$
3. $\floor{N / \left(\floor{N/i} + 1 \right) } < i$

只证第 3 个。
设 $ \floor{\frac{N}{i}} = t$，我们有
$ t \le \frac{N}{i} < t + 1 \iff it \le N < i(t + 1) \iff i\frac{t}{t + 1} \le \frac{N}{t + 1} < i \implies \floor{\frac{N}{t + 1}} < i$

因此我们有 $i \le \floor{\frac{N}{x}} < i + 1$，即对于 $\floor{\frac{N}{i + 1}} < x \le \floor{\frac Ni}$ 恒有 $ \floor{\frac{N}{x}} = i $，这里我们得到一个很有用的等式

若 $\floor{\frac{N}{i}} \ge \floor{\frac{N}{i+1}}$，则
$f[l][\floor{\frac{N}{i}}] = f[l][\floor{N/(i + 1)}] + \left( \floor{\frac{N}{i}} - \floor{\frac{N}{i+1}} \right) f[l - 1][i] $
并且当 $\floor{\frac{N}{i}} > \floor{\frac{N}{i+1}}$ 时，$i$ 可表为 $\floor{ \frac{N}{ \floor{ \frac{N}{i} } } }$

从而有
\begin{aligned}
f_2[l][i] &= f_2[l][i+1] + \left( \floor{\frac{N}{i}} - \floor{\frac{N}{i+1}} \right) f[l - 1][i] \\
&= f_2[l][i+1] + \left( \floor{\frac{N}{i}} - \floor{\frac{N}{i+1}} \right) f_1[l - 1][i]
\end{aligned}

$f_2$ 的边界条件有两个：

1. $f_2[1][i] = \floor{ \frac{N}{i} } $
2. \begin{aligned} f_2[l][\floor{\sqrt{N}}] &:= f[l][\floor{\frac{N}{\floor{\sqrt N}}}] \\
   &= f[l][\floor{\frac{N}{\floor{\sqrt N}+1}}] + \left( \floor{ \frac{N}{ \floor{\sqrt{N}} } } - \floor{ \frac{N}{\floor{\sqrt N}+1} } \right) f[l - 1][\floor{ \sqrt{N} } ] \\
   &= f_1[l][\floor{\frac{N}{\floor{\sqrt N}+1}}] + \left(\floor{\frac{N}{\floor{\sqrt{N}}}} - \floor{\frac{N}{\floor{\sqrt{N}} + 1}} \right) f_1[l - 1][\floor{ \sqrt{N} } ]
   \end{aligned}

代码

int main() {

    int n, k;
    scan(n, k);
    int r = sqrt(n + 0.5); // r is defined to be floor(sqrt{n})
    vv<int> f1(k + 1, vi(r + 1)); // f1[len][i]：长为len，首项 <= i
    vv<int> f2(k + 1, vi(r + 1)); // f2[len][i]：长为len，首项 <= n/i
 
    up (i, 1, r) {
        f1[1][i]=i;
    }
    up (i, 1, r) {
        f2[1][i] = n / i;
    }
    up (l, 2, k) {
        up (i, 1, r) {
            f1[l][i] = f1[l][i - 1] + f2[l - 1][i];
            if (f1[l][i] >= mod) {
                f1[l][i] -= mod;
            }
        }
        f2[l][r] = f1[l][n/(r + 1)] + (ll)(n / r - (n / (r + 1))) * f1[l - 1][r] % mod;
        if (f2[l][r] >= mod) {
            f2[l][r] -= mod;
        }
        down (i, r - 1, 1) {
            f2[l][i] = f2[l][i + 1] + (ll)(n / i - (n / (i + 1))) * f1[l - 1][i] % mod;
            if (f2[l][i] >= mod) {
                f2[l][i] -= mod;
            }
        }
    }
    println(f2[k][1]);
 
    return 0;
}

ABC133F Small Products

原文：https://www.cnblogs.com/Patt/p/11788010.html