description
给定 \(n\leq 10^6\), 求有多少个 \(1\) 到 \(n\) 的排列，对于一个 1 到 \(n\) 的排列 \(p\)，\(f(p)\) 表示 \(p\) 的任意前缀内的元素的最大公约数构成的集合的大小。求有多少个排列 \(p_0\) 满足 \(f(p_0)=\max\{f(p)\}\)。
模大质数。
solution
容易发现，这个最大值为 \(\lfloor\log_2 n\rfloor +1\)（一种可行的方案是排列的第一个元素放 \(2^{\lfloor\log_2 n\rfloor}\)，后面 \(\log_2{n}\) 个元素，每一个元素都是前一个的一半）。
我们再来考虑满足最大值的前提下，第一个位置可以放哪些元素。
首先一定可以放 \(2^{\lfloor\log_2 n\rfloor}\)。再向后每一位至少要除以前一位的一个质因子（比如 4 后面放 6，除去了 2 这一个质因子）。所以能放在第一位的数的所有质因子指数和应该恰等于 \(\lfloor\log_2 n\rfloor\)。
由此我们可以发现，第一个数除了放 \(2^{\lfloor\log_2 n\rfloor}\) 外，如果 \(2^{\lfloor\log_2 n\rfloor-1}\times 3 \leq n\)，还可以选择 \(2^{\lfloor\log_2 n\rfloor-1}\times 3\)。
这样我们就确定了满足最大值的所有排列可能的第一个元素。
确定第一位之后，任意前缀的最大公约数就一定整除第一位元素， 并且从第二位起任意一位的元素，其质因子 2 和 3 的指数至多有一个减少 1。
由此我们可以设计出 dp 状态 \(f_{i,a,b} ~(b\in\{0,1\})\) 表示对排列的前 \(i\) 个元素，其最大公约数为 \(2^a3^b\) 且满足第二位起任意一位元素所含 2 和 3 的指数至多有一个比前一位元素减少 1。
容易写出转移方程：
-
\(f_{i,a,0}=f_{i-1,a,0}\times(\lfloor \frac{n}{2^a} \rfloor-(i-1))+f_{i-1,a+1,0}\times (\lfloor \frac{n}{2^a} \rfloor-\lfloor \frac{n}{2^{a+1}} \rfloor)+f_{i-1,a,1}\times(\lfloor \frac{n}{2^a} \rfloor-\lfloor \frac{n}{2^a3} \rfloor)\)
-
\(f_{i,a,1}=f_{i-1,a,1}\times(\lfloor \frac{n}{2^a3} \rfloor-(i-1))+f_{i-1,a+1,1}\times(\lfloor \frac{n}{2^{a}3} \rfloor-\lfloor \frac{n}{2^{a+1}3} \rfloor)\)
答案即为 \(f_{n,0,0}\)。
hint
此题的关键就在于发现第一位元素只可能形如 \(2^a\) 或 \(2^a3\)，进而设计出 dp 状态，完成求解。