Description

Link：CF1174E

Solution

本质不同的前缀 gcd 是 $\mathcal{O}(\log n)$ 级别的，因为当前缀 gcd 改变时，新的 gcd 一定为旧的 gcd 的约数。

考虑在唯一分解角度下观察 gcd，设 gcd 为 $\sum p_i^{c_i}$，为了使得本质不同的前缀 gcd 最多，当 gcd 变化时，肯定是选择某一个 $c_i \gets c_i - 1$。故为了使得本质不同的 gcd 最多，就是要使得排列的第一个数的 $\sum c_i$ 最多。

首先，肯定不会存在质因子 $p_i \geq 5$，因为此时可以将 $p_i$ 换成 $2^2$，$\sum c_i$ 更大且仍然合法。

其次，肯定不会存在 $3$ 的次数 $\geq 2$，因为此时可以将 $3^2$ 换成 $2^3$，$\sum c_i$ 更大且仍然合法。

故第一个数只能被表示成 $2^x3^y$，其中 $y \in \{0, 1\}$。状态数为 $\mathcal{O}(\log n)$。

设 $f(i, x, y)$ 表示，填到排列的前 $i$ 位，且当前的 gcd 为 $2^x3^y$ 时的方案数。设 $\mathrm{calc}(x) = \left\lfloor \frac{n}{x} \right\rfloor$ 表示 $1, \cdots, n$ 中 $x$ 的倍数的个数。

$$f(i + 1, x, y) \gets_{+} f(i, x, y) \cdot (\mathrm{calc}(2^x3^y) - i) \\ f(i + 1, x - 1, y) \gets_{+} f(i, x, y) \cdot (\mathrm{calc}(2^{x - 1}3^y) - \mathrm{calc}(2^x3^y)) \\ f(i + 1, x, y - 1) \gets_{+} f(i, x, y) \cdot (\mathrm{calc}(2^x3^{y - 1}) - \mathrm{calc}(2^x3^y))$$

初态：记 $u = \lfloor \log_2 n \rfloor$，则有 $f(1, u, 0) = 1$；若 $2^{u - 1}3 \leq n$ 时，还有 $f(1, u - 1, 1) = 1$。

终态：$f(n, 0, 0)$。