Ehab and the Expected GCD Problem题解

xukehg · 2024-11-26 18:18:44 · 题解

题解的复杂度都是 O(n \log n) 或者好写的 O(n) 的 dp 做法，我来一发好理解的极为难写的 O(n) 纯数学做法。

题目大意

• 对于一个 1 \sim n 的排列 p，称其权值为前缀 \gcd 的不同值个数。
• 设所有排列的最大权值为 x，问有多少个排列 p 的权值真的能达到 x。

题目解决

设 p 的前缀 \gcd 为 q，一个显然的观察是 q_i 整除 q_{i-1}。更进一步地，由于 q_i 每次降低会变为原来的至多 \dfrac{1}{2}，所以 x \le \log_2 n。x = \left\lfloor\log_2 n\right\rfloor 的构造也是容易的，只需令 q 依次为 2 的幂次即可。

考虑符合题意的 q 的数量。设 k_i = \dfrac{p_i}{p_{i+1}}，讨论 k_i 的取值：

• 若其中不含有 \ge 3 的值，即为上述构造的情况。
• 若其中含有 \ge 3 的值，不难发现这样的值出现次数至多为 1：如果出现 \ge 2 次，由于 3 ^ 2 > 2 ^ 3，可知显然不优。

考虑对 q_i 去重（下同），去重后情况数是 O(\log n) 级别的，不妨大力枚举。

记 S_i 表示为 q_i 的倍数但不为 q_{i-1} 倍数的数构成的集合，并设 h_i=|S_i|，共有 l 个数（事实上 l = x）。枚举改变前缀 \gcd 的那些数，称之为关键数，可知第 i 个关键数有 h_i 种可能，先令 res = \prod h_i。

把 \gcd 相同的区间分成若干个块，则从后往前数第 i 个块的第一个数即为关键数。不难发现，对于任意块都有关键数是该块中下标的最小值，考虑倒着插入数字。

首先，S_l 中的数显然只能放在第一个块中。由于关键数已经确定，所以新加进来的数只能放到关键数的后面。因此，对于第一个数的放置，只有一种情况；第二个数的放置，有 2 种情况，即第一个数的前面或后面。显然可以发现，每放一个数，就增加了一个可以放数的位置。综上，S_l 中的数的放置有 (h_1 - 1)! 种情况。注意已经放了一个数当关键数。

考虑 S_{l - 1} 中的数的放置。它不仅可以在第 l - 1 块中放置，而且可以在 l 号块放置，对于 S_{i} 中数的放置也同理。注意到已有的可以放置的位置的数量是固定的，我们可以设计出递推的方法：记 i - 1 号块到第 1 号块的位置数量为 kw，则第 i 号块的方案数为 kw \times (kw + 1) \times\dots\times(kw + h_i - 2) 种情况，可以预处理阶乘逆元 O(1) 得出。

许多细节：

• 如果 h_i = 1，跳过对这个块贡献的计算，并注意其仍然提供了一个位置；

然后我们就愉快的通过了这道 2500 的题目。

记录。