题解：CF763C Timofey and remoduling

给出一个 $n$ 和一个质数 $m$，以及一个长度为 $n$，互不相同的 $a$ 序列，求是否存在一种 $a$ 的排列方式使得 $a$ 是一个 $\bmod\ m$ 意义下的等差数列。如果存在，输出任意一组可能的首项 $x$ 及公差 $d$，否则输出 $-1$。

下文假设 $n\not=m$ 且 $n\not=1$。记 $p_i$ 表示 $a_i$ 在对应等差数列的项数，$f_i$ 表示对应未取模等差数列的第 $i$ 项，即 $f_i=x+(i-1)d$。

令 $t=a_2-a_1,k=p_2-p_1$，可以看出 $t\equiv k\times d\pmod m$。

因为 $k$ 是多少跟后续处理没太大关系，考虑求出 $k$ 并解出公差。
如果这个等差数列不取模，易得其中满足 $a_i-a_j=k\times d$ 的 $(i,j)$ 对数恰为 $n-k$ 个，因为这个条件等价于 $(i,j)$ 在等差数列中相距 $k$ 个位置，直接统计即可得到 $k$；但是因为已知的是取模后的序列，所以需要考虑一下什么时候结果会不一样：
存在 $i$ 使得 $p_i\le k$（即未取模时不存在对应的 $j$ 使得 $a_j=a_i-k\times d$），并且存在正整数 $z\le n-p_i$ 使得 $a_i-k\times d\equiv f_{z+p_i}\pmod m$（即存在一个只是和对应值同余却不相等的数），又因为 $d\perp m$，所以 $z$ 如果存在，那么一定唯一。
所以出现错误的必要不充分条件是存在一组 $(i,z)$ 使得 $a_i-k\times d\equiv f_{z+p_i}\pmod m$，把式子变形一下：

因为 $0\le z,k\le n-1$，所以当 $m>2n-2$ 的时候，可以直接使用相同的方法求 $k$。

考虑 $m\le 2n-2$ 的时候怎么做：

注意到 $f$ 在模意义下有周期性，即：
对于 $1\le i<j\le m$，

对于 $1\le i\le m$，

这表明 $f_1\sim f_m$ 在模意义下是一个 $0\sim m-1$ 的排列，并且 $f$ 中所有相邻值连起来形成一个环，环上每个连续段都是合法的。注意到 $a$ 的合法性与 $a$ 相对于 $[0,m)$ 的补集的合法性相同，而取补集之后的序列长度 $n^\prime=m-n$，考虑它和 $m$ 的大小关系：

满足前文中直接统计方法的正确条件，可以直接按照补集处理套回去求 $k$。

根据已知的 $k$ 和 $k\times d$，可以直接求出 $d$，然后找到唯一的一个 $i$ 使得 $a$ 中不存在 $(a_i-d+m)\mod m$，因为这和前文求 $k$ 部分的方式形式是一样的，所以若 $a$ 有解，满足条件的 $i$ 一定唯一，以它为首项即可。如果前面过程中取了补集，真正的首项只需要加一个 $d\times n^\prime$，公差不变。