Description
给你一个长度为 $n$ 的等差数列，但是它们被打乱了，并且被模了一个质数 $m$。奇妙的是，在对 $m$ 取模后这个数列里没有相同的数。现在请你还原出这个等差数列的首相和公差，给出任一合法解即可。若无解则输出“-1”。
Solution
有趣的思维题。
CF 上的数据好强，自己的乱搞被卡到自闭，无奈之下写了正解。
考虑先将给出的序列（不妨称之为序列 $a$）排序，然后考虑 $a_1$ 和 $a_2$ 在对 $m$ 取模前的数列中相距多远。
不妨设距离为 $k$，公差为 $d$，令 $g = a_2 - a_1$，则 $g ≡ dk \pmod m$。
若这个差 $g$ 的出现次数为 $r$，那么显然 $k = n - r$。
$r$ 的值可以用二分或者用哈希来求，Code 部分采用的二分法。
然后我们就可以得出来 $d = gk^{-1}$。
但由于可能存在无解的情况，因此我们要用 $O(n)$ 的时间检验一下答案。
就这？
并不是。
由于是在模 $m$ 意义下的，可能会存在一个项加了 $g$ 再模了以后恰好等于了序列 $a$ 的某个值，但是它实际上是不存在后 $k$ 项的。
这就矛盾了，于是我们考虑找出这个矛盾的界限。考虑极限情况，是原等差数列的末项错误地跳到了首项，即：
然后由于 $g$ 应该是原序列中两个数的差，然后又因为我们是错误地跳到了首项，所以这个 $g$ 最大应该是 $(n - 2)d$，即在等差数列中末项的前一项与首项之间的差。
将 $g$ 代入上式，可得：
化简一下，得：
由于 $0 \leq d < m$，而 $d = 0$ 的情况我们已经特判掉了，所以问题出在 $(2n - 3)$ 身上，所以当 $2n - 3 \geq m$ 时，我们都可以找到两个差的和在模 $m$ 的意义下为 0，这就导致了答案错误。
怎么办？考虑如果原等差数列是有解的，由于 $m$ 是质数，那么按照公差，从首项一直跳，一定能跳完，然后再跳完序列 $a$ 的补集，再跳回首项。
由于我们难以解决序列 $a$ 在 $2n - 3 \geq m$ 时候的问题，考虑一下能否把问题转换到补集上。
由于补集的大小是 $n’ = (m - n)$ 的，所以有 $2n’ - 3 = 2(m - n) - 3 = 2m - (2n + 3)$，又因为 $2n - 3 \geq m$，所以 $2n + 3 > m$，所以我们发现补集的大小 $n’$ 是满足 $2n’ - 3 < m$ 的。因此我们可以把问题转化到补集上，再根据补集上等差数列的首项去推序列 $a$ 的首项，推的方法同前两段中的内容。
记得特判 $n = 1$、$n = m$ 和补集的大小 $n’ = 1$ 的情况。
然后这题就做完了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
| #include <cstdio>
#include <iostream>
#include <algorithm>
#define maxN 100010
using namespace std;
long long n = 0, m = 0;
long long a[maxN], b[maxN];
bool cmp (long long x, long long y)
{
return x < y;
}
bool find (long long x)
{
long long l = 1, r = n;
while(l < r)
{
long long mid = (l + r) >> 1;
if(a[mid] < x)
{
l = mid + 1;
}
else
{
r = mid;
}
}
return (a[l] == x);
}
long long pow (long long x, long long y)
{
if(!y)
{
return 1;
}
else
{
long long dq = pow(x, y >> 1);
if(!(y % 2))
{
return dq * dq % m;
}
else
{
return dq * dq % m * x % m;
}
}
}
long long inv (long long x)
{
return pow(x, m - 2);
}
int main ()
{
scanf("%lld %lld", &m, &n);
for(long long i = 1;i <= n; i++)
{
scanf("%lld", &a[i]);
}
if(n == 1)
{
printf("%lld 0", a[1]);
return 0;
}
if(n == m)
{
printf("0 1");
return 0;
}
if(2 * n - 3 < m)
{
sort(a + 1, a + n + 1, cmp);
long long g = a[2] - a[1], cnt = 0;
for(long long i = 1;i <= n; i++)
{
cnt += find((a[i] + g) % m);
}
long long k = n - cnt;
long long d = g * inv(k) % m;
long long now = a[1];
cnt = 1;
while(true)
{
if(!find((now + d) % m))
{
break;
}
now = (now + d) % m, cnt++;
}
if(cnt == n)
{
printf("%lld %lld", a[1], d);
return 0;
}
now = a[1];
long long res = 0;
while(true)
{
if(!find((now - d + m) % m))
{
break;
}
now = (now - d + m) % m, cnt++;
res = now;
}
if(cnt == n)
{
printf("%lld %lld", res, d);
return 0;
}
printf("-1");
}
else
{
sort(a + 1, a + n + 1, cmp);
int N = 0;
for(int i = 0;i < m; i++)
{
if(!find(i))
{
b[++N] = i;
}
}
for(int i = 1;i <= N; i++)
{
a[i] = b[i];
}
int nowN = n;
n = N;
sort(a + 1, a + n + 1, cmp);
long long g = a[2] - a[1], cnt = 0;
if(n == 1)
{
printf("%lld 1", (a[1] - nowN % m + m) % m);
return 0;
}
for(long long i = 1;i <= n; i++)
{
cnt += find((a[i] + g) % m);
}
long long k = n - cnt;
long long d = g * inv(k) % m;
long long now = a[1];
cnt = 1;
while(true)
{
if(!find((now + d) % m))
{
break;
}
now = (now + d) % m, cnt++;
}
if(cnt == n)
{
printf("%lld %lld", (a[1] - (nowN * d) % m + m) % m, d);
return 0;
}
now = a[1];
long long res = 0;
while(true)
{
if(!find((now - d + m) % m))
{
break;
}
now = (now - d + m) % m, cnt++;
res = now;
}
if(cnt == n)
{
printf("%lld %lld", (res - (nowN * d) % m + m) % m, d);
return 0;
}
printf("-1");
}
return 0;
}
|