LOJ 6087 毒瘤题 与 加强版

普通版题目链接

k=1

所有数异或起来，最后的异或和就是答案

k=2

如果和上一样的做法，最后会得到两个数异或的结果。
既然是两个不同数，那么二进制下也一定有一位不一样。
我们开按位置来异或，\(a[i]\)表示第\(i\)位为\(1\)的数的异或和，\(b[i]\)表示第\(i\)位为\(0\)的数的异或和。
因为同一个数一定会在一个桶里面异或，那么出现偶数次的是没有影响的。
最后只有两个出现奇数次的数产生贡献。
找到某一位\(bit[a,i]!=bit[b,i]\)
于是就找到了两个出现奇数次的数

#include <bits/stdc++.h>
using namespace std;

int n, k;

int main() {
    scanf("%d %d", &n, &k);
    if (k == 1) {
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			int x;
			scanf("%d", &x);
			sum ^= x;
		}
		printf("%d\n", sum);
	} else {
		int a[32] = {}, b[32] = {};
		for (int i = 1; i <= n; i++) {
			int x;
			scanf("%d", &x);
			for (int j = 31; j >= 0; j--) {
				if (x & (1 << j)) {
                    a[j] ^= x;
				} else b[j] ^= x;
			}
		}
		for (int i = 0; i <= 31; i++) {
			if (b[i] && a[i]) {
				if (a[i] > b[i]) swap(a[i], b[i]);
				printf("%d %d\n", a[i], b[i]);
				break;
			}
		}
	}
	return 0;
}

k=500 or k=5000

需要一点奇技淫巧。
和算法二一样，我们目的是让出现偶数次的数不产生贡献，而出现奇数次的能够单独出现。
取几个模数，每个数\(x\)都把哈希值对应的桶异或上 x 对应的hash值 。
同一个数一定是在同一个桶里面异或，出现偶数次的一样没有影响。
那么怎么判断最后桶里面是几个数异或在一起的呢？

这需要构造一下 hash 函数
如果对于输入的\(x\)，hash值为\(Ax+B\)
其中\(A\),\(B\)是大质数，且\(A>B\)。

如果最后桶里面的值是\(val\bmod A=B\)，因为多个数异或在一起后，大概率都不能满足这个条件...
这样可能会漏一些答案，但是不会多选出不合法答案，因为出现偶数次的数是对桶没有贡献的。
这样多选几个数，大概率就能让出现奇数次的数取模后 hash 值不同。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int A = 99823533, B = 1926817, N = 13;
int mod[N] = {12107, 10627, 21079, 27077, 28007, 21009, 25080, 20395, 22308, 20486, 20468, 21905, 10201};
ll f[N][25990], x;
int n, k;
vector<ll> v;

int main() {
    scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &x);
		ll H = A * 1ll * x + B;
	    for (int i = 0; i < N; i++) f[i][H % mod[i]] ^= H;	
	}
	for (int i = 0; i < N; i++)
		for (int j = 0; j < mod[i]; j++) {
			if (f[i][j] % A == B) v.push-back(f[i][j] / A);
		}
	sort(v.begin(), v.end());
	unique(v.begin(), v.end());
	for (int i = 0; i < k; i++) printf("%lld\n", v[i]);
	return 0;
}