解题 P7521【 [省选联考 2021 B 卷] 取模 】

· · 题解

Tips : 本解法不一定是正解。

考虑暴力，枚举 a_k, 将 \{a_n\} 中除了 a_k 的数字对 a_k 取模，生成新序列 \{b_n\}。将 \{b_n\} 中的数字分成两部分 A, B。A 中元素小于 \lceil\frac{n}{2}\rceil, B 中元素大于等于 \lceil\frac{n}{2}\rceil。然后考虑模 a_k 意义下，最大值三种可能的情况:

  3. 枚举 b_i 找到 \{b_n\} 小于 a_k-b_i 的最大值 b_x，b_i+b_x 可能为最大值。

视实现情况，复杂度为 \Theta(n^2\log n) ~ \Theta(n^3)。

考虑对上述暴力进行优化。

优化一

相同出现过的数字只枚举一次。

看起来用处不大，复杂度依然不变。

优化二

从大到小枚举 a_k, 然后记录一个答案 p。一旦 a_k \le p 则不再枚举。

看起来用处不大，但结合优化一以后，复杂度下降到 \mathcal{O}(n\log n\log V)。其中 V 是 \{a_n\} 的值域大小。

这里的复杂度是一个比较松的上界，应该能找到更紧的界。

以下是这个上界的证明。

证明

考虑弱化上述的优化，即把记录的答案 p 改成暴力中情况 1、2 的最大值，记作 p=\max\{p_1,p_2\}。

首先枚举 \{a_n\} 中最大值为 a_k，记作 a_x。

延续暴力算法中的定义，有 A 中所有元素均小于等于 p_1, 所以小于等于 p。即 A 中元素无需枚举。所以只考虑 B 中元素。

设

\lceil\frac{a_x}{2}\rceil\le B_1\le B_2\le \cdots\le B_t\le a_x

假设枚举若干轮后 p 变为 p'。则我们需要枚举的元素为

p'\le B_s\le B_{s+1}\le \cdots\le B_t\le a_x

将上述不等式逐项相减得到 \{u_1,u_2,\cdots,u_{t-s+1}\}。

因为第二类最大值为 B_i+B_{i+1}-B_{i+2}\le p'。

所以 u_i+2u_{i+1}\ge\sum\limits_{j=1}^{i+1}u_j。

要让 u 尽可能小，上述不等式得取等号。

即 u_{i+1}=\sum\limits_{j=1}^{i-1}u_j。

此时可知 u_{i+1}=u_i+u_{i-1} 形似斐波那契数列，所以 u_n=c\left(\frac{\sqrt{5}+1}{2}\right)^n+o(1)，其中 c 是某个常数。

又因为

B_t-p'=\sum\limits_{i=1}^{t-s+1} u_i = u_{t-s+3}\le\frac{V}{2}

所以 t-s，即需要枚举的 a_k 的数量是 \mathcal{O}(\log V) 级的。

总时间复杂度为 \mathcal{O}(n\log n \log V)。