test/math/xor-basis/unit-test-xor-basis.test.cpp

• View this file on GitHub
• Last update: 2024-09-10 10:42:34+08:00
• Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

• xor basis (線性基) (library/math/xor-basis.hpp)
• random_t (library/random/random.hpp)
• library/random/splitmix64.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb" // dummy

#include <iostream>
#include <vector>
#include <chrono>
#include <cassert>
#include <algorithm>
#include "../../../library/math/xor-basis.hpp"
#include "../../../library/random/random.hpp"
using namespace std;
using namespace felix;

template<int N_MAX, int LOG_MAX>
void TEST() {
	static_assert(N_MAX >= 1 && LOG_MAX >= 1);
	static constexpr long long LIMIT = 1LL << LOG_MAX;

	int n = rnd.next(1, N_MAX);
	std::vector<long long> a(n);
	xor_basis<LOG_MAX> basis;
	for(int i = 0; i < n; i++) {
		a[i] = rnd.next(LIMIT);
		basis.insert(a[i]);
	}
	std::vector<long long> ans;
	ans.reserve((1 << n) - 1);
	for(int mask = 1; mask < (1 << n); mask++) {
		long long xor_sum = 0;
		for(int i = 0; i < n; i++) {
			if(mask >> i & 1) {
				xor_sum ^= a[i];
			}
		}
		ans.push_back(xor_sum);
	}
	std::sort(ans.begin(), ans.end());
	ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
	for(int i = 0; i < (int) a.size(); i++) {
		assert(basis.contains(a[i]));
	}
	for(int i = 0; i < (int) ans.size(); i++) {
		assert(basis.get_kth(i) == ans[i]);
		assert(basis.contains(ans[i]));
	}
	assert(basis.get_kth(ans.size()) == -1);
	assert(basis.get_min() == ans[0]);
	assert(basis.get_max() == ans.back());
}

int main() {
	TEST<1, 1>();
	TEST<1, 60>();
	for(int iter = 0; iter < 50; iter++) {
		TEST<20, 60>();
	}

	int a, b;
	cin >> a >> b;
	cout << a + b << "\n";
	return 0;
}

#line 1 "test/math/xor-basis/unit-test-xor-basis.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb" // dummy

#include <iostream>
#include <vector>
#include <chrono>
#include <cassert>
#include <algorithm>
#line 3 "library/math/xor-basis.hpp"
#include <array>


namespace felix {

template<int B>
struct xor_basis {
public:
	void insert(long long x) {
		for(int i = B - 1; i >= 0; i--) {
			if(x >> i & 1) {
				if(!p[i]) {
					p[i] = x;
					cnt++;
					change = true;
					return;
				} else {
					x ^= p[i];
				}
			}
		}
		if(zero == false) {
			zero = change = true;
		}
	}

	long long get_min() {
		if(zero) {
			return 0;
		}
		for(int i = 0; i < B; i++) {
			if(p[i]) {
				return p[i];
			}
		}
	}

	long long get_max() {
		long long ans = 0;
		for(int i = B - 1; i >= 0; i--) {
			ans = std::max(ans, ans ^ p[i]);
		}
		return ans;
	}

	long long get_kth(long long k) {
		k++;
		if(k == 1 && zero) {
			return 0;
		}
		if(zero) {
			k--;
		}
		if(k >= (1LL << cnt)) {
			return -1;
		}
		update();
		long long ans = 0;
		for(int i = 0; i < (int) d.size(); i++) {
			if(k >> i & 1) {
				ans ^= d[i];
			}
		}
		return ans;
	}

	bool contains(long long x) {
		if(x == 0) {
			return zero;
		}
		for(int i = B - 1; i >= 0; i--) {
			if(x >> i & 1) {
				x ^= p[i];
			}
		}
		return x == 0;
	}

	void merge(const xor_basis& other) {
		for(int i = 0; i < B; i++) {
			if(other.p[i]) {
				insert(other.p[i]);
			}
		}
	}

private:
	bool zero = false, change = false;
	int cnt = 0;
	std::array<long long, B> p = {};
	std::vector<long long> d;

	void update() {
		if(!change) {
			return;
		}
		change = false;
		d.clear();
		for(int j = 0; j < B; j++) {
			for(int i = j - 1; i >= 0; i--) {
				if(p[j] >> i & 1) {
					p[j] ^= p[i];
				}
			}
		}
		for(int i = 0; i < B; i++) {
			if(p[i]) {
				d.push_back(p[i]);
			}
		}
	}
};

} // namespace felix

#line 3 "library/random/random.hpp"
#include <set>
#include <cstring>
#line 7 "library/random/random.hpp"
#include <numeric>
#include <climits>
#include <string>
#line 3 "library/random/splitmix64.hpp"

namespace felix {

namespace internal {

// http://xoshiro.di.unimi.it/splitmix64.c

struct splitmix64_hash {
	static unsigned long long splitmix64(unsigned long long x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	unsigned long long operator()(unsigned long long x) const {
		static const unsigned long long FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

} // namespace internal


} // namespace felix

#line 11 "library/random/random.hpp"

namespace felix {

struct random_t {
public:
	explicit random_t(unsigned long long seed = 3905348978240129619LL) {
		set_seed(seed);
	}

	void set_seed(unsigned long long seed) {
		for(int i = 0; i < 4; i++) {
			s[i] = internal::splitmix64_hash::splitmix64(seed);
			seed += 0x9e3779b97f4a7c15;
		}
	}

	// [0, n)
	unsigned long long next(unsigned long long n) {
		const unsigned long long LIMIT = std::numeric_limits<unsigned long long>::max() / n * n;
		unsigned long long r;
		do {
			r = next();
		} while(r >= LIMIT);
		return r % n;
	}

	// [l, r]
	template<class T>
	T next(T l, T r) {
		assert(l <= r);
		return T(l + next(r - l + 1ULL));
	}

	template<class Iter>
	void shuffle(Iter l, Iter r) {
		if(l == r) {
			return;
		}
		int pos = 0;
		for(auto it = l + 1; it != r; it++) {
			pos += 1;
			int j = next(pos + 1);
			if(j != pos) {
				std::iter_swap(it, l + j);
			}
		}
	}

	// [0, n)
	std::vector<int> perm(int n) {
		std::vector<int> a(n);
		std::iota(a.begin(), a.end(), 0);
		shuffle(a.begin(), a.end());
		return a;
	}

	// [l, r]
	template<class T>
	std::vector<T> distinct(int size, T l, T r) {
		std::vector<T> result;
		if(size == 0) {
			return result;
		}
		assert(l <= r);
		assert(size > 0);
		unsigned long long n = r - l + 1;
		assert(size <= n);
		double expected = 0;
		for(int i = 1; i <= size; i++) {
			expected += double(n) / double(n - i + 1);
		}
		if(expected < (double) n) {
			std::set<T> s;
			while((int) s.size() < size) {
				T val = T(next(l, r));
				if(s.insert(val).second) {
					result.push_back(val);
				}
			}
		} else {
			std::vector<T> p(perm(n));
			for(auto& x : p) {
				x += l;
			}
			result.insert(result.end(), p.begin(), p.begin() + size);
		}
		return result;
	}

	std::string string(int n, char min_char = 'a', char max_char = 'z') {
		std::string s(n, '_');
		for(int i = 0; i < n; i++) {
			s[i] = next(min_char, max_char);
		}
		return s;
	}

private:
	std::array<unsigned long long, 4> s;

	static unsigned long long rotl(const unsigned long long x, int k) {
		return (x << k) | (x >> (64 - k));
	}

	unsigned long long next() {
		const unsigned long long result = rotl(s[1] * 5, 7) * 9;
		const unsigned long long t = s[1] << 17;
		s[2] ^= s[0];
		s[3] ^= s[1];
		s[1] ^= s[2];
		s[0] ^= s[3];
		s[2] ^= t;
		s[3] = rotl(s[3], 45);
		return result;
	}
} rnd;

} // namespace felix
#line 10 "test/math/xor-basis/unit-test-xor-basis.test.cpp"
using namespace std;
using namespace felix;

template<int N_MAX, int LOG_MAX>
void TEST() {
	static_assert(N_MAX >= 1 && LOG_MAX >= 1);
	static constexpr long long LIMIT = 1LL << LOG_MAX;

	int n = rnd.next(1, N_MAX);
	std::vector<long long> a(n);
	xor_basis<LOG_MAX> basis;
	for(int i = 0; i < n; i++) {
		a[i] = rnd.next(LIMIT);
		basis.insert(a[i]);
	}
	std::vector<long long> ans;
	ans.reserve((1 << n) - 1);
	for(int mask = 1; mask < (1 << n); mask++) {
		long long xor_sum = 0;
		for(int i = 0; i < n; i++) {
			if(mask >> i & 1) {
				xor_sum ^= a[i];
			}
		}
		ans.push_back(xor_sum);
	}
	std::sort(ans.begin(), ans.end());
	ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
	for(int i = 0; i < (int) a.size(); i++) {
		assert(basis.contains(a[i]));
	}
	for(int i = 0; i < (int) ans.size(); i++) {
		assert(basis.get_kth(i) == ans[i]);
		assert(basis.contains(ans[i]));
	}
	assert(basis.get_kth(ans.size()) == -1);
	assert(basis.get_min() == ans[0]);
	assert(basis.get_max() == ans.back());
}

int main() {
	TEST<1, 1>();
	TEST<1, 60>();
	for(int iter = 0; iter < 50; iter++) {
		TEST<20, 60>();
	}

	int a, b;
	cin >> a >> b;
	cout << a + b << "\n";
	return 0;
}

Back to top page