一根长度为 xxx 的木材最终会被切割成 xxx 根长度为 111 的木材,而且在这个过程中最多会产生 O(logx)O(\log x)O(logx) 种不同长度的木棍。这启发我们预先把所有木材可能产生的长度处理出来,然后预处理出 SiS_iSi 表示如果经过了若干次切割后最长的木材长度变为 iii 那么一共会产生多少根长度为 111 的木材。询问 kkk 就只需要在这个数组上二分。复杂度视实现而定。
使用您的 Hydro 通用账户