T3.最小环

题面：

给定一个长度为 $n$ 的正整数序列 $a_i$，下标从 $1$ 开始编号。我们将该序列视为一个首尾相邻的环，更具体地，对于下标为 $i,j(i\le j)$ 的两个数 $a_i,a_j$，它们的距离为 $\text{min}\{j-i,i-j+n\}$。

现在再给定 $m$ 个整数 $k_{1,...,m}$，对每个 $k_i(i=1,2,...,m)$，你需要将上面的序列 $a_i$ 重新排列，使得环上任意两个距离为 $k_i$ 的数字的乘积之和最大。

$n\le 2\times 10^5$。

举例/说明：

如果 $n=6$，并且 $a_i=i$，$k=1$。则经过枚举可以得到一种最优方案是 $\{3,1,2,4,6,5\}$，答案是 $3\times 1+1\times 2+2\times 4+4\times 6+6\times 5+5\times 3=82$。

如果 $k=2$，则可以得到一种最优方案是 $\{3,6,1,4,2,5\}$，答案是 $3\times 1+1\times 2+2\times 3+6\times 4+4\times 5+5\times 6=85$。

如果 $k=3$，一种最优方案是 $\{1,5,3,2,6,4\}$，这里注意答案是 $88$ 而不是 $44$。

解答：

$\texttt{Solution 1}$

$\text{10 pts}$

一种很容易想到的做法，就是暴力枚举。先枚举一遍所有可能性，再根据每种可能性计算答案，再取一个最大值即可。没有任何思考技术含量。时间复杂度 $O(n!)$，可以通过 $n\le 10$ 的测试点。

我觉得第二个测试点是 $n\le 18$，可能也是给暴力分的，可以剪枝或者先推一推结论减小枚举范围，这样 $20$ 分也就有了。

这样肯定是不行的。作为提高组的题目，肯定需要更进一步的思考。

$\texttt{Solution 2}$

$\text{30 pts}$

我们已经说过，优化时间的常见方法是转化为dp或者数学问题。

先来一个特殊情况：$k=1$。我们不妨把数据排一个序，然后一个一个插进序列中。假设插入的是 $a_i$，$a_i$ 插入的位置与 $a_x,a_y$ 相邻，则它对答案的贡献是 $a_i\times (a_x+a_y)-a_x\times a_y$。可以这么理解：插入 $a_i$ 的时候，$a_i$ 与 $a_x,a_y$ 都相邻了，答案增加 $a_i\times (a_x+a_y)$；而 $a_x$ 与 $a_y$ 开始相邻，现在不相邻了，所以答案减去 $a_x\times a_y$。

那么我们自然就会想到：$a_i\times (a_x+a_y)-a_x\times a_y$ 什么时候取最大值呢？考虑化简：$-(a_i-a_x)(a_i-a_y)+a_i^2$。由于已经排好序了，即对于任意的 $i<j$ 均有 $a_i\le a_j$，则易得 $a_i-a_x,a_i-a_y\ge 0$。也就是说，$a_x,a_y$ 越大，答案就越大。所以说最优取值就是 $x=i-1,y=i-2$。

综上考虑，再插入每一个数时，插进序列中最大的两个数之间。比如当 $n=6$ 且 $a_i=i$ 时，插入的顺序是这样的：

$\{1\}$

$\{1,2\}$

$\{1,3,2\}$

$\{1,3,4,2\}$

$\{1,3,5,4,2\}$

$\{1,3,5,6,4,2\}$

可以保证每次序列中最大的两个数都是相邻的。所以说直接统计答案即可，没必要模拟插入的过程。时间复杂度 $O(n\log n)$，瓶颈是排序的过程。

$\texttt{Solution 3}$

$\text{80 pts}$

好。既然我们已经处理了 $k=1$ 的情况，我们就再看看 $k>1$ 时如何做。就以 $n=10$ 为例子吧，如果 $k=2,4$，则是这样的情况：

通过观察可以发现，对于这两种情况，可以将第 $1,3,5,7,9$ 个元素为一组，$2,4,6,8,10$ 为一组，这样的话对于每一组，就相当于是 $k=1$ 的情况了。所以说，对于任意的 $n,k$，我们可以将其分为 $\text{gcd}(n,k)$ 组，每组有 $Q=\dfrac{n}{\text{gcd}(n,k)}$ 个数，对于每一组处理 $k=1$ 的情况即可。

但是我们又遇到一个问题：每一组的数取什么值好呢？

如果枚举每一组的数是多少，那么时间复杂度就会非常之大。所以我们还需要进行贪心。

考虑每一组的数经过排列后是 $a_1,a_2,...,a_Q$，那么答案就是 $a_1\times a_2+...+a_{Q-1}\times a_Q+a_Q\times a_1$。想必你们都听过小学奥数常说的一句话：积一定，差大和大。也就是说，对于一些数，它们的积是固定的，如果它们之间的差越大，也即数据越不平均，那么它们的和就越大。所以说我们自然想到了：设 $n$ 个数从小到大排序是 $a_1,...,a_n$。那么对于每一组的数，下标都是连续的。什么意思呢？就是将这些数分为 $\{a_1,...,a_Q\},\{a_{Q+1},...,a_{2Q}\},...$ 这些组，那么它们的答案之和就是最大的。

如果再回想一下的话，这种方法是有正确性的。考虑我们交换这些组中的两个数，可以证明答案减少了。

这样的复杂度是多少呢？对于每一组的处理是 $O(Q)$，一共分成 $\text{gcd}(n,k)$ 组，所以每次查询的时间复杂度是 $O(n)$，总体时间复杂度是 $O(n^2)$。仍然不可行。

$\texttt{Solution 4}$

$\text{100 pts}$

都 $80$ 分了，离 $\color{green}{\text{AC}}$ 就不远了。

就看 $n=10$ 的例子，如果我有两个询问，分别是 $k=2,4$，那么两个的答案就是一样的，因为 $\text{gcd}(10,2)=\text{gcd}(10,4)=2$。所以优化时间的方法就出来了：初始化。

我们枚举 $i=1-\dfrac{n}{2}$，如果 $\text{gcd}(n,i)$ 已经处理过了，那么就跳过；否则就处理一遍答案，并记录。这样对于每次查询，直接调用记录的结果就行，时间复杂度 $O(1)$。

那么初始化的时间复杂度是多少呢？就是 $n$ 的因数个数再乘上 $n$，可以理解为 $O(n\sqrt{n})$，足够通过这道题。网上有关于因数个数为 $O(\sqrt{n})$ 的研究，有兴趣的同学可以去看一看。

总结一下，我们还是从暴力开始，这次我们走的是数学推导的道路，最终完全脱离了暴力的想法。之后想到优化就不难了，关键是数学推导的部分。