HUSTFC2023-M

· · 题解

【HUSTACM】此题解为官方题解。

简要题意

求有多少个最多允许一个位置不满足严格递增的正整数序列使得其乘积小于等于 n 。

Sol

这个题做法好像很多， 有各种各样的乱搞。

不妨从大到小来依次生成这个序列， 考虑 f(n, m, 0/1) 表示接下来填数的乘积最多是 n， 最大可以填 m ， 有没有使用那个不满足严格递增限制的位置。

那么一方面可以填小于等于根号的数， 如果填 i ， 则可以转移到 f (\lfloor \frac{n}{i} \rfloor, i, 0/1) 。

还可以填大于根号的数， 如果填 i ， 则可以转移到 f (\lfloor \frac{n}{i} \rfloor, min \{\lfloor \frac{n}{i} \rfloor, i\}, 0/1) 。由于 i > \sqrt {n} ， 也就是转移到 f (\lfloor \frac{n}{i} \rfloor, \lfloor \frac{n}{i} \rfloor, 0/1) 。于是这一部分可以整除分块计算。

那么第一, 二维都是通过 n / i 得到或者由一个小于等于根号的数得到， 故总状态数是 \sqrt{n}^2 = n 级别的， 并且不难想象实际用到的位置会显著低于这个数字。

然后考虑第一种转移的总转移量， 考虑第一维度为 n时， 约为 \sqrt{n} + \sqrt{\sqrt{n}} + ....， 不妨约等于为 \sqrt{n} ， 那么考虑所有 n 第一维转移量之和，约为 \sqrt{n} + \sqrt{\frac{n}{2}} + \sqrt{\frac{n}{3}}+... 显然不超过 n 。

再考虑第二种转移的转移量， 如果仅进行第二种转移， 那么复杂度同杜教筛的分析， 如果先进行第二种转移再进行第一种转移， 则会访问到仅进行第一种转移访问到的位置 ，我们采用记忆化的方法， 则这部分的复杂度不超过 O (n ^ {\frac{3}{4}}) 。如果先进行第一种转移再进行第二种转移， 由于最大数的限制， 这部分复杂度也不会超过 O (n) 。

故本做法上限复杂度不会超过 O (n) ， 在记忆化 n \leq 5000 的答案以后不精细实现在不开 O2 条件下可以在 2s 内通过 n = 10^8 的数据， 且可以轻松扩展到有 k 个不合法位置的情况。

另一个有意思的事情是， 如果直接搜索有多少严格递增序列的乘积小于等于 n ， 只会搜出来大约 10^7 种情况， 可以基于这个性质暴力/乱搞直接通过这个题甚至可能比std快还短 。

欢迎大家开发新做法薄纱std