等差数列问题

Published: by Creative Commons Licence

  • 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$。由于

通过上面的公式,我们可以直接求出$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}$。如果存在这样的一个排列,就输出任意一个,否则报告无解。

一道原题

不会。