等差数列问题

Published: July 06, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 模意义下的等差数列

模意义下的等差数列

题目1：给定素数$m$，并给定$n$个不同的数$a_1,\ldots,a_n$，满足$0\leq a_i<m$。现在我们希望将整个数组进行排列，得到新的数列$b_1,\ldots,b_n$，满足对所有的$1<i<n$，有$b_i-b_{i-1}=b_{i+1}-b_{i}$。如果存在这样的一个排列，就输出任意一个，否则报告无解。

这是一道CF原题。

如果$n\leq 1$，答案很显然，因此我们仅考虑$2\leq n$的情况。

设我们找到的等差数列的公式为$f(i)=x+id$，其中$b_i=f(i-1)$。可以发现一定有$d>0$，考虑到$m$是素数，因此$m$和$d$一定互质，即我们保证了$f(0),f(1),\ldots,f(m-1)$都是不同的数。

若$n\leq \frac{m}{2}$满足，则考虑$a_1,a_2$，设二者分别对应$b$的第$i$和$i+k$项，则一定有$a_2-a_1=kd$。注意到$b_1,\ldots,b_n$对应的是$f(0),\ldots,f(n-1)$，其中正好有$n-k$项的差值正好为$kd$，因此我们可以通过哈希表枚举有多少数对的差值正好为$kd$，从而计算出$k$，进而得出$d$。

知道了$k$，下面考虑怎么算$x$。由于

$$\begin{aligned} \sum_{i=0}^{n-1}a_i&=\sum_{i=0}^{n-1}x+id\\ &=nx+\frac{n(n-1)d}{2} \end{aligned}$$

通过上面的公式，我们可以直接求出$x$。接下来我们验证一下解是否可行即可。总的时间复杂度为$O(n)$。

下面考虑当$n\geq \frac{m}{2}$的时候，我们可以考虑$a$中元素的补集$\overline{a}$即可，可以发现其对应的等差数列为$f(n),f(n+1),\ldots,f(m-1)$。求出$\overline{a}$对应的等差数列，之后递推前面几项即可，时间复杂度相同。

题目1：给定任意数$m$，并给定$n$个不同的数$a_1,\ldots,a_n$，满足$0\leq a_i<m$。现在我们希望将整个数组进行排列，得到新的数列$b_1,\ldots,b_n$，满足对所有的$1<i<n$，有$b_i-b_{i-1}=b_{i+1}-b_{i}$。如果存在这样的一个排列，就输出任意一个，否则报告无解。

一道原题。

不会。