Bubble Cup 11 - Finals [Online Mirror, Div. 1] B. Space Isaac Hash

Description
有两个集合，两个集合里的数互不相同且都是0~m-1的数，现在给你第一个集合的数，每次你可以从第一个集合和第二个集合各选一个数出来，问有哪些数不能表示出来。

---

Sample Input
2 5
3 4

---

Sample Output
1
2

---

好强啊这题。。。
首先有一个比较显然的想法，一个数不能被表示出来，当且仅当对于每一个A集合中的数ai都能找到另一个A集合中的数匹配。
也就是说，最多只有n个，且n个可能的权值为：
a1+a1,a1+a2,a1+a3,…,a1+an，那么剩下你就要判对于一个权值是否满足条件。
那么我们可以假设当前枚举到第i个数，那么这个数的权值即为：
a1+ai，那么对于1~i的数我们肯定是a2和ai-1匹配得到a1+ai，a3和ai-2匹配得到a1+ai，为什么，很好证明。
假设a2没有跟ai-1匹配而是跟ai-2匹配，那么ai-1就无人可以匹配了，因为想跟ai-1匹配就一定需要一个更小的数，然而并没有，就不满足条件。
然后对于i~n的数，我们也是用类似的方法。
然后你将这个数列差分一下就相当于判回文了，你可以用Hash维护。。。

---

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const ULL P = 131;
int _min(int x, int y) {return x < y ? x : y;}
int _max(int x, int y) {return x > y ? x : y;}
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}

ULL s1[210000], s2[210000], o[210000];
int a[210000], b[210000], ans[210000];

int main() {
	int n = read(), m = read();
	for(int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
	sort(a + 1, a + n + 1);
	for(int i = 1; i < n; i++) a[i] = a[i + 1] - a[i];
	o[0] = 1; for(int i = 1; i < n; i++) s1[i] = s1[i - 1] * P + a[i], o[i] = o[i - 1] * P;
	for(int i = n - 1; i >= 1; i--) s2[i] = s2[i + 1] * P + a[i];
	int len = 0; bool bk = 0;
	for(int i = 2; i <= n; i++) if((b[1] + b[1]) % m != (b[n - i + 2] + b[i]) % m) bk = 1;
	if(!bk) ans[++len] = (b[1] + b[1]) % m;
	for(int i = 2; i < n; i++) {
		int hh = (b[1] + b[i]) % m;
		if((b[i + 1] + b[n]) % m != hh) continue;
		if(s1[i - 1] != s2[1] - s2[i] * o[i - 1]) continue;
		if(s2[i + 1] != s1[n - 1] - s1[i] * o[n - i - 1]) continue;
		ans[++len] = hh;
	} if(s1[n - 1] == s2[1]) ans[++len] = (b[1] + b[n]) % m;
	len = unique(ans + 1, ans + len + 1) - (ans + 1);
	sort(ans + 1, ans + len + 1); printf("%d\n", len);
	for(int i = 1; i <= len; i++) printf("%d ", ans[i]);
	return 0;
}