This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb" #include "my_template.hpp" #include "random/base.hpp" #include "nt/nimber/base.hpp" #include "nt/nimber/solve_quadratic.hpp" template <typename U> void test() { using F = Nimber<U>; auto test = [&](F x) -> void { assert(x * x == x.square()); assert(x.sqrt().square() == x); if (x != F(0)) assert(x * x.inverse() == F(1)); }; FOR(i, 1 << 20) { test(i); } FOR(10000) { test(F(RNG_64())); } auto test_q = [&](F a, F x) -> void { F b = x * x + a * x; vc<F> ANS = solve_quadratic(a, b); for (auto& z: ANS) { assert(z * z + a * z == b); } FOR(j, len(ANS)) FOR(i, j) { assert(ANS[i] != ANS[j]); } int exist = 0; FOR(i, len(ANS)) exist += (ANS[i] == x); assert(exist == 1); }; // quadratic FOR(a, 100) { FOR(x, 100) { test_q(a, x); } } FOR(10000) { test_q(F(RNG_64()), F(RNG_64())); } } void solve() { int a, b; cin >> a >> b; cout << a + b << "\n"; } signed main() { test<u16>(); test<u32>(); test<u64>(); solve(); }
#line 1 "test/1_mytest/nimber.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/aplusb" #line 1 "my_template.hpp" #if defined(LOCAL) #include <my_template_compiled.hpp> #else // https://codeforces.com/blog/entry/96344 #pragma GCC optimize("Ofast,unroll-loops") // いまの CF だとこれ入れると動かない? // #pragma GCC target("avx2,popcnt") #include <bits/stdc++.h> using namespace std; using ll = long long; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i128 = __int128; using u128 = unsigned __int128; using f128 = __float128; template <class T> constexpr T infty = 0; template <> constexpr int infty<int> = 1'010'000'000; template <> constexpr ll infty<ll> = 2'020'000'000'000'000'000; template <> constexpr u32 infty<u32> = infty<int>; template <> constexpr u64 infty<u64> = infty<ll>; template <> constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000; template <> constexpr double infty<double> = infty<ll>; template <> constexpr long double infty<long double> = infty<ll>; using pi = pair<ll, ll>; using vi = vector<ll>; template <class T> using vc = vector<T>; template <class T> using vvc = vector<vc<T>>; template <class T> using vvvc = vector<vvc<T>>; template <class T> using vvvvc = vector<vvvc<T>>; template <class T> using vvvvvc = vector<vvvvc<T>>; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; #define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__)) #define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__)))) // https://trap.jp/post/1224/ #define FOR1(a) for (ll _ = 0; _ < ll(a); ++_) #define FOR2(i, a) for (ll i = 0; i < ll(a); ++i) #define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i) #define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c)) #define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i) #define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i) #define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i) #define overload4(a, b, c, d, e, ...) e #define overload3(a, b, c, d, ...) d #define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__) #define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define elif else if #define eb emplace_back #define mp make_pair #define mt make_tuple #define fi first #define se second #define stoi stoll int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } int popcnt_mod_2(int x) { return __builtin_parity(x); } int popcnt_mod_2(u32 x) { return __builtin_parity(x); } int popcnt_mod_2(ll x) { return __builtin_parityll(x); } int popcnt_mod_2(u64 x) { return __builtin_parityll(x); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2) int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template <typename T> T floor(T a, T b) { return a / b - (a % b && (a ^ b) < 0); } template <typename T> T ceil(T x, T y) { return floor(x + y - 1, y); } template <typename T> T bmod(T x, T y) { return x - y * floor(x, y); } template <typename T> pair<T, T> divmod(T x, T y) { T q = floor(x, y); return {q, x - q * y}; } template <typename T, typename U> T SUM(const vector<U> &A) { T sm = 0; for (auto &&a: A) sm += a; return sm; } #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define LB(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit() template <typename T> T POP(deque<T> &que) { T a = que.front(); que.pop_front(); return a; } template <typename T> T POP(pq<T> &que) { T a = que.top(); que.pop(); return a; } template <typename T> T POP(pqg<T> &que) { T a = que.top(); que.pop(); return a; } template <typename T> T POP(vc<T> &que) { T a = que.back(); que.pop_back(); return a; } template <typename F> ll binary_search(F check, ll ok, ll ng, bool check_ok = true) { if (check_ok) assert(check(ok)); while (abs(ok - ng) > 1) { auto x = (ng + ok) / 2; (check(x) ? ok : ng) = x; } return ok; } template <typename F> double binary_search_real(F check, double ok, double ng, int iter = 100) { FOR(iter) { double x = (ok + ng) / 2; (check(x) ? ok : ng) = x; } return (ok + ng) / 2; } template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } // ? は -1 vc<int> s_to_vi(const string &S, char first_char) { vc<int> A(S.size()); FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); } return A; } template <typename T, typename U> vector<T> cumsum(vector<U> &A, int off = 1) { int N = A.size(); vector<T> B(N + 1); FOR(i, N) { B[i + 1] = B[i] + A[i]; } if (off == 0) B.erase(B.begin()); return B; } // stable sort template <typename T> vector<int> argsort(const vector<T> &A) { vector<int> ids(len(A)); iota(all(ids), 0); sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); }); return ids; } // A[I[0]], A[I[1]], ... template <typename T> vc<T> rearrange(const vc<T> &A, const vc<int> &I) { vc<T> B(len(I)); FOR(i, len(I)) B[i] = A[I[i]]; return B; } template <typename T, typename... Vectors> void concat(vc<T> &first, const Vectors &... others) { vc<T> &res = first; (res.insert(res.end(), others.begin(), others.end()), ...); } #endif #line 3 "test/1_mytest/nimber.test.cpp" #line 2 "random/base.hpp" u64 RNG_64() { static u64 x_ = u64(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL; x_ ^= x_ << 7; return x_ ^= x_ >> 9; } u64 RNG(u64 lim) { return RNG_64() % lim; } ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); } #line 2 "nt/nimber/nimber_impl.hpp" namespace NIM_PRODUCT { u16 E[65535 * 2 + 7]; u16 L[65536]; u64 S[4][65536]; u64 SR[4][65536]; u16 p16_15(u16 a, u16 b) { return (a && b ? E[u32(L[a]) + L[b] + 3] : 0); } u16 p16_15_15(u16 a, u16 b) { return (a && b ? E[u32(L[a]) + L[b] + 6] : 0); } u16 mul_15(u16 a) { return (a ? E[3 + L[a]] : 0); } u16 mul_15_15(u16 a) { return (a ? E[6 + L[a]] : 0); } u32 p32_mul_31(u32 a, u32 b) { u16 al = a & 65535, ah = a >> 16, bl = b & 65535, bh = b >> 16; u16 x = p16_15(al, bl); u16 y = p16_15_15(ah, bh); u16 z = p16_15(al ^ ah, bl ^ bh); return u32(y ^ z) << 16 | mul_15(z ^ x); } u32 mul_31(u32 a) { u16 al = a & 65535, ah = a >> 16; return u32(mul_15(al ^ ah)) << 16 | mul_15_15(ah); } u16 prod(u16 a, u16 b) { return (a && b ? E[u32(L[a]) + L[b]] : 0); } u32 prod(u32 a, u32 b) { u16 al = a & 65535, ah = a >> 16, bl = b & 65535, bh = b >> 16; u16 c = prod(al, bl); return u32(prod(u16(al ^ ah), u16(bl ^ bh)) ^ c) << 16 | (p16_15(ah, bh) ^ c); } u64 prod(u64 a, u64 b) { u32 al = a & 0xffffffff, ah = a >> 32, bl = b & 0xffffffff, bh = b >> 32; u32 c = prod(al, bl); return u64(prod(al ^ ah, bl ^ bh) ^ c) << 32 ^ (p32_mul_31(ah, bh) ^ c); } u16 square(u16 a) { return S[0][a]; } u32 square(u32 a) { return S[0][a & 65535] ^ S[1][a >> 16]; } u64 square(u64 a) { return S[0][a & 65535] ^ S[1][a >> 16 & 65535] ^ S[2][a >> 32 & 65535] ^ S[3][a >> 48 & 65535]; } u16 sqrt(u16 a) { return SR[0][a]; } u32 sqrt(u32 a) { return SR[0][a & 65535] ^ SR[1][a >> 16]; } u64 sqrt(u64 a) { return SR[0][a & 65535] ^ SR[1][a >> 16 & 65535] ^ SR[2][a >> 32 & 65535] ^ SR[3][a >> 48 & 65535]; } // inv: 2^16 の共役が 2^16+1 であることなどを使う. x^{-1}=y(xy)^{-1} という要領. u16 inverse(u16 a) { return E[65535 - L[a]]; } u32 inverse(u32 a) { if (a < 65536) return inverse(u16(a)); u16 al = a & 65535, ah = a >> 16; u16 norm = prod(al, al ^ ah) ^ E[L[ah] * 2 + 3]; int k = 65535 - L[norm]; al = (al ^ ah ? E[L[al ^ ah] + k] : 0), ah = E[L[ah] + k]; return al | u32(ah) << 16; } u64 inverse(u64 a) { if (a <= u32(-1)) return inverse(u32(a)); u32 al = a & 0xffffffff, ah = a >> 32; u32 norm = prod(al, al ^ ah) ^ mul_31(square(ah)); u32 i = inverse(norm); return prod(al ^ ah, i) | u64(prod(ah, i)) << 32; } void __attribute__((constructor)) init_nim_table() { // 2^16 未満のところについて原始根 10279 での指数対数表を作る // 2^k との積 u16 tmp[] = {10279, 15417, 35722, 52687, 44124, 62628, 15661, 5686, 3862, 1323, 334, 647, 61560, 20636, 4267, 8445}; u16 nxt[65536]; FOR(i, 16) { FOR(s, 1 << i) { nxt[s | 1 << i] = nxt[s] ^ tmp[i]; } } E[0] = 1; FOR(i, 65534) E[i + 1] = nxt[E[i]]; memcpy(E + 65535, E, 131070); memcpy(E + 131070, E, 14); FOR(i, 65535) L[E[i]] = i; FOR(t, 4) { FOR(i, 16) { int k = 16 * t + i; u64 X = prod(u64(1) << k, u64(1) << k); FOR(s, 1 << i) S[t][s | 1 << i] = S[t][s] ^ X; } } FOR(t, 4) { FOR(i, 16) { int k = 16 * t + i; u64 X = u64(1) << k; FOR(63) X = square(X); FOR(s, 1 << i) SR[t][s | 1 << i] = SR[t][s] ^ X; } } } } // namespace NIM_PRODUCT #line 3 "nt/nimber/base.hpp" template <typename UINT> struct Nimber { using F = Nimber; UINT val; constexpr Nimber(UINT x = 0) : val(x) {} F &operator+=(const F &p) { val ^= p.val; return *this; } F &operator-=(const F &p) { val ^= p.val; return *this; } F &operator*=(const F &p) { val = NIM_PRODUCT::prod(val, p.val); return *this; } F &operator/=(const F &p) { *this *= p.inverse(); return *this; } F operator-() const { return *this; } F operator+(const F &p) const { return F(*this) += p; } F operator-(const F &p) const { return F(*this) -= p; } F operator*(const F &p) const { return F(*this) *= p; } F operator/(const F &p) const { return F(*this) /= p; } bool operator==(const F &p) const { return val == p.val; } bool operator!=(const F &p) const { return val != p.val; } F inverse() const { return NIM_PRODUCT::inverse(val); } F pow(u64 n) const { assert(n >= 0); UINT ret = 1, mul = val; while (n > 0) { if (n & 1) ret = NIM_PRODUCT::prod(ret, mul); mul = NIM_PRODUCT::square(mul); n >>= 1; } return F(ret); } F square() { return F(NIM_PRODUCT::square(val)); } F sqrt() { return F(NIM_PRODUCT::sqrt(val)); } }; #ifdef FASTIO template <typename T> void rd(Nimber<T> &x) { fastio::rd(x.val); } template <typename T> void wt(Nimber<T> &x) { fastio::wt(x.val); } #endif using Nimber16 = Nimber<u16>; using Nimber32 = Nimber<u32>; using Nimber64 = Nimber<u64>; #line 1 "linalg/xor/basis.hpp" // basis[i]: i 番目に追加成功したもの. 別のラベルがあるなら外で管理する. // array<UINT, MAX_DIM> rbasis: 上三角化された基底. [i][i]==1. // way<UINT,UINT> rbasis[i] を basis[j] で作る方法 template <int MAX_DIM> struct Basis { static_assert(MAX_DIM <= 128); using UINT = conditional_t<(MAX_DIM <= 32), u32, conditional_t<(MAX_DIM <= 64), u64, u128>>; int rank; array<UINT, MAX_DIM> basis; array<UINT, MAX_DIM> rbasis; array<UINT, MAX_DIM> way; Basis() : rank(0), basis{}, rbasis{}, way{} {} // return : (sum==x にできるか, その方法) pair<bool, UINT> solve(UINT x) { UINT c = 0; FOR(i, MAX_DIM) { if ((x >> i & 1) && (rbasis[i] != 0)) { c ^= way[i], x ^= rbasis[i]; } } if (x == 0) return {true, c}; return {false, 0}; } // return : (sum==x にできるか, その方法). false の場合には追加する pair<bool, UINT> solve_or_add(UINT x) { UINT y = x, c = 0; FOR(i, MAX_DIM) { if ((x >> i & 1) && (rbasis[i] != 0)) { c ^= way[i], x ^= rbasis[i]; } } if (x == 0) return {true, c}; int k = lowbit(x); basis[rank] = y, rbasis[k] = x, way[k] = c | UINT(1) << rank, ++rank; return {false, 0}; } }; #line 3 "nt/nimber/solve_quadratic.hpp" namespace NIMBER_QUADRATIC { // x^2+x==a を解く. Trace(a)==0 が必要. // Nimber では Trace は topbit. // topbit==0 である空間から偶数全体への全単射がある. // これを前計算したい. 線形写像なので連立方程式を解いて埋め込むだけでよい. u64 Q[4][65536]; void __attribute__((constructor)) precalc() { Basis<63> B; FOR(i, 63) { Nimber64 x(u64(1) << (i + 1)); x = x.square() + x; assert(!B.solve_or_add(x.val).fi); } FOR(k, 63) { int t = k / 16, i = k % 16; u64 X = B.way[k] * 2; FOR(s, 1 << i) Q[t][s | 1 << i] = Q[t][s] ^ X; } } u16 f(u16 a) { return Q[0][a]; } u32 f(u32 a) { return Q[0][a & 65535] ^ Q[1][a >> 16]; } u64 f(u64 a) { return Q[0][a & 65535] ^ Q[1][a >> 16 & 65535] ^ Q[2][a >> 32 & 65535] ^ Q[3][a >> 48 & 65535]; } template <typename U> vc<U> solve_quadratic_1(U a) { constexpr int k = numeric_limits<U>::digits - 1; if (a >> k & 1) return {}; return {f(a), U(f(a) | 1)}; } } // namespace NIMBER_QUADRATIC template <typename F> vc<F> solve_quadratic(F a, F b) { if (a == F(0)) return {b.sqrt()}; b /= a.square(); vc<F> ANS; for (auto& x: NIMBER_QUADRATIC::solve_quadratic_1(b.val)) { ANS.eb(a * F(x)); } return ANS; } #line 7 "test/1_mytest/nimber.test.cpp" template <typename U> void test() { using F = Nimber<U>; auto test = [&](F x) -> void { assert(x * x == x.square()); assert(x.sqrt().square() == x); if (x != F(0)) assert(x * x.inverse() == F(1)); }; FOR(i, 1 << 20) { test(i); } FOR(10000) { test(F(RNG_64())); } auto test_q = [&](F a, F x) -> void { F b = x * x + a * x; vc<F> ANS = solve_quadratic(a, b); for (auto& z: ANS) { assert(z * z + a * z == b); } FOR(j, len(ANS)) FOR(i, j) { assert(ANS[i] != ANS[j]); } int exist = 0; FOR(i, len(ANS)) exist += (ANS[i] == x); assert(exist == 1); }; // quadratic FOR(a, 100) { FOR(x, 100) { test_q(a, x); } } FOR(10000) { test_q(F(RNG_64()), F(RNG_64())); } } void solve() { int a, b; cin >> a >> b; cout << a + b << "\n"; } signed main() { test<u16>(); test<u32>(); test<u64>(); solve(); }