HS：这题考察基本功（诶自然数拆分怎么做我看看）。

一个基础的观察：对于物品 $i$，当 $i\ge\sqrt{n}$ 时物品不可能取完，所以这部分是一个完全背包。

问题分成了两部分，设 $B=\lceil\sqrt{n}\rceil$，令 $F_i$ 表示只用 $1\sim B$ 这些物品体积为 $i$ 的方案数，$G_i$ 表示只用 $B+1\sim n$ 这些物品体积为 $i$ 的方案数，最后对 $F,G$ 卷一下即可。

对于 $F_i$：就是一个裸的完全背包，单调队列可以 $O(n\sqrt{n})$，但因为计数背包是可以退的，所以直接记录前缀和就可以 $O(n\sqrt{n})$。

对于 $G_i$：选择的物品不超过 $\sqrt{n}$ 个，考虑设 $g_{i,j}$ 表示这部分选择 $i$ 个物品体积和为 $j$ 的方案数，为了避免记重强制选择的物品体积单调递减。

问题变成了对一个单调递减，和为 $j$，最小数超过 $\sqrt{n}$ 的序列计数。如何刻画单调递减，经典做法是维护一个空数列，每次全局加一，或者在末尾加入一个最小元素，因此可以得出转移式 $g_{i,j}=g_{i,j-i}+g_{i-1,j-B-1}$。状态数是 $O(n\sqrt{n})$，转移是 $O(1)$ 的。

综上，在 $O(n\sqrt{n})$ 的时间复杂度内解决了本题。