题解：CF763C Timofey and remoduling
zcz0263
·
2025-02-18 20:29:53
·
题解
题意
给出一个 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 ，把式子变形一下：
\begin{aligned}
a_i-k\times d&\equiv f_{z+p_i}&\pmod m\\
a_i-k\times d&\equiv a_i+z\times d&\pmod m\\
-k\times d&\equiv z\times d&\pmod m\\
-k&\equiv z&\pmod m\\
z+k&\equiv0&\pmod m\\
m&\mid(z+k)
\end{aligned}
因为 0\le z,k\le n-1 ，所以当 m>2n-2 的时候，可以直接使用相同的方法求 k 。
考虑 m\le 2n-2 的时候怎么做：
注意到 f 在模意义下有周期性，即：1\le i<j\le m ，
\begin{aligned}
i\times d&\not\equiv j\times d&\pmod m\\
x+i\times d&\not\equiv x+j\times d&\pmod m\\
f_i&\not\equiv f_j&\pmod m
\end{aligned}
对于 1\le i\le m ，
\begin{aligned}
i\times d&\equiv i\times d&\pmod m\\
x+i\times d&\equiv x+(m+i)d&\pmod m\\
f_i&\equiv f_{m+i}&\pmod m
\end{aligned}
这表明 f_1\sim f_m 在模意义下是一个 0\sim m-1 的排列，并且 f 中所有相邻值连起来形成一个环，环上每个连续段都是合法的。注意到 a 的合法性与 a 相对于 [0,m) 的补集的合法性相同，而取补集之后的序列长度 n^\prime=m-n ，考虑它和 m 的大小关系：
\begin{aligned}
m&\le2n-2\\
m-2n+2&\le0\\
2(m-n)+2&\le m\\
2n^\prime+2&\le m\\
2n^\prime-2&<m
\end{aligned}
满足前文中直接统计方法的正确条件，可以直接按照补集处理套回去求 k 。
根据已知的 k 和 k\times d ，可以直接求出 d ，然后找到唯一的一个 i 使得 a 中不存在 (a_i-d+m)\mod m ，因为这和前文求 k 部分的方式形式是一样的，所以若 a 有解，满足条件的 i 一定唯一，以它为首项即可。如果前面过程中取了补集，真正的首项只需要加一个 d\times n^\prime ，公差不变。