CodeForces 1045B Space Isaac
原题链接
0∼m−1的数被分成两个集合，你可以分别从两个集合中取一个数相加并对 m 取模，求 0∼m−1 中不能构造出的数。
题解
感觉如果 sxd666 来做这题肯定能一眼秒，然而他正忙着切其他题。
首先我们发现如果要让 a+b≡x(modm)，如果已知a,x，那b 一定是唯一的。也就是说，假设给定集合是 A，与之对应的集合为B，如果有a∈A 但找不到 b∈A 使得 a+b≡x(modm)。那么x∈A+B（定义A+B={a+b:a∈A,b∈B}）。反过来讲，如果x∈/A+B，那么一定能把A 中所有元素配对（可能两个数相同），也即x∈/A+B⟺A=x−A（定义x−A={x−a:a∈A}）。
然后我们如果把小于 m 的整数看成一个环，如果有两个数 a,b 使a+b≡x(modm)，a顺时针时针移动，b肯定逆时针移动（即运动方向相反，且移动的长度应该是相等的（(a+k)modm+(b−k)modm≡a+b(modm)嘛）。
于是我们画两个圆，都表示集合 {ai}（假设ai 已经排好序），我们要把第一个圆的点与第二个圆的点匹配。
假设 ai 与aj匹配。我们把 i 移动至 i+1，那么根据上面推出的单调性，j 必须移至 j−1（因为ai∼ai+1 之间没有数了，所以 j 也只能移动一格），又因为移动距离必须相等，即ai+1−ai=aj−aj−1。
所以我们令 bi=ai−ai−1（b1=(a1−an)modm），设串s1=bnbn−1bn−2⋯b1,s2=b1b2b3⋯bn，我们要找的是s1 与s2成环后相等，并找到一对匹配的数，他们加起来模 m 即为一组解。我们令 s3=s2+s2，找到s3 中所有等于 s1 的子串，就得到了所有解，这个问题用 KMP 或是 Z 都能解决。
代码
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
| #include <cstdio>
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 200005;
LL aa[maxn];
LL bb[maxn];
vector<LL> gou;
int in[maxn << 2];
LL Z[maxn << 2];
set<LL> ans;
int main()
{
int n;
LL m;
scanf("%d%lld", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%lld", &aa[i]);
bb[1] = ((aa[1] - aa[n]) + m) % m;
for(int i = 2; i <= n; ++i)
bb[i] = ((aa[i] - aa[i-1]) % m + m) % m;
for(int i = n; i; --i)
{
gou.push_back(bb[i]);
in[gou.size() - 1] = i;
}
gou.push_back(-1LL);
for(int i = 1; i <= n; ++i)
{
gou.push_back(bb[i]);
in[gou.size() - 1] = i;
}
for(int i = 1; i <= n; ++i)
{
gou.push_back(bb[i]);
in[gou.size() - 1] = i;
}
Z[0] = gou.size();
for(int i = 1, j = 1, k; i < (int) gou.size(); i = k)
{
j = max(j, i);
while(gou[j] == gou[j - i])
++j;
Z[i] = j - i;
k = i + 1;
while(k + Z[k - i] < j)
{
Z[k] = Z[k - i];
++k;
}
}
for(int i = 1; i < (int) gou.size(); ++i)
if(Z[i] >= n)
ans.insert((aa[in[i] - 1 ? in[i] - 1 : n] + aa[n]) % m);
printf("%d\n", (int) ans.size());
for(auto it = ans.begin(); it != ans.end(); ++it)
printf("%lld ", *it);
return 0;
}
|
