P7521 [省选联考 2021 B 卷] 取模

· · 题解

--- [题目传送门](https://www.luogu.com.cn/problem/P7521) $a$ 的位置对我们没有影响，先排序。 考虑直接上暴力，枚举模数项 $a_{mid}$，直接对其它数进行 $\text {mod}$ 得到新数组 $b$。 那么对于 $a_{mid}$ 的贡献分成两类： 1. $b_i+b_j < a_{mid}
  1. b_i+b_j > a_{mid}

发现我们省了个等于的情况，因为这种根本没用。

第二种显然是 b_{up}+b_{up-1}，原因？

对于 b 数组的每两个数相加都不会超过 2 \times a_{mid}，既然已经保证 b_i+b_j > a_{mid}，也就是说相当于一堆 a_{mid} \le x \le 2 \times a_{mid}，只要选和最大的两个即可，显然就是最大的两个数。

再回头过来看第一种。

这个显然可以搞双指针。

于是复杂度就是 O(n^2 \log n)（因为还有个排序）。

再想如何优化，倒序枚举 mid，如果当前最大值 ans \ge a_{mid}-1，即大于贡献的上届，就珂以直接 \text{break} 掉了。

这个优化效果十分明显，直接过了。

然后你交到 UOJ 上，发现只有 95\ tps，为什么？

显然还有个明显的 hack ：你在很多次的重判同一个模数。

加上一个 map 即可。

AC\ Code

最后再来一波证明：

考虑到 a_1...\le a_{mid-1}\le ans \le a_{mid} \le a_{mid+1}...\le a_n 。

根据刚刚的结论，显然有：

\text{对于} \forall i\ \in \ [mid, n-1),\ ans \ge (a_i+a_{i+1}) \mod a_{i+2}

考虑到 a_i \le a_{i+1} \le a_{i+2}，珂以把取模省掉。

ans \ge a_i+a_{i+1}-a_{i+2} ans+a_{i+2} \ge a_i+a_{i+1} ans+a_{i+2}-2 \times ans \ge (a_i -ans)+(a_{i+1}-ans)

令 f_i=a_i-ans 。

f_{i+2} \ge f_i + f_{i+1}

这长得很像 Fibonacci 数列，而我们知道，Fibonacci 数列是以指数级增长的。

又 f_{n}=a_n-ans \le 10^8 。

所以 f_{mid} \approx \log{10^8} ，也就是说，我们大概会扫 \log 次，而单次的复杂度为 O(n \log n) ， 所以总复杂度 O(n \log n \log{10^8}) 。