This documentation is automatically generated by online-judge-tools/verification-helper
#include "graph/maximum_matching_size.hpp"
#include "random/base.hpp"
#include "mod/modint61.hpp"
#include "linalg/matrix_rank.hpp"
template <typename GT>
int maximum_matching_size(GT& G) {
static_assert(!GT::is_directed);
using mint = modint61;
int N = G.N;
vv(mint, tutte, N, N);
for (auto&& e: G.edges) {
mint x = RNG(mint::get_mod());
int i = e.frm, j = e.to;
tutte[i][j] += x;
tutte[j][i] -= x;
}
return matrix_rank(tutte, N, N) / 2;
}
#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 "mod/modint61.hpp"
struct modint61 {
static constexpr u64 mod = (1ULL << 61) - 1;
u64 val;
constexpr modint61() : val(0ULL) {}
constexpr modint61(u32 x) : val(x) {}
constexpr modint61(u64 x) : val(x % mod) {}
constexpr modint61(int x) : val((x < 0) ? (x + static_cast<ll>(mod)) : x) {}
constexpr modint61(ll x) : val(((x %= static_cast<ll>(mod)) < 0) ? (x + static_cast<ll>(mod)) : x) {}
static constexpr u64 get_mod() { return mod; }
modint61 &operator+=(const modint61 &a) {
val = ((val += a.val) >= mod) ? (val - mod) : val;
return *this;
}
modint61 &operator-=(const modint61 &a) {
val = ((val -= a.val) >= mod) ? (val + mod) : val;
return *this;
}
modint61 &operator*=(const modint61 &a) {
const unsigned __int128 y = static_cast<unsigned __int128>(val) * a.val;
val = (y >> 61) + (y & mod);
val = (val >= mod) ? (val - mod) : val;
return *this;
}
modint61 operator-() const { return modint61(val ? mod - val : u64(0)); }
modint61 &operator/=(const modint61 &a) { return (*this *= a.inverse()); }
modint61 operator+(const modint61 &p) const { return modint61(*this) += p; }
modint61 operator-(const modint61 &p) const { return modint61(*this) -= p; }
modint61 operator*(const modint61 &p) const { return modint61(*this) *= p; }
modint61 operator/(const modint61 &p) const { return modint61(*this) /= p; }
bool operator<(const modint61 &other) const { return val < other.val; }
bool operator==(const modint61 &p) const { return val == p.val; }
bool operator!=(const modint61 &p) const { return val != p.val; }
modint61 inverse() const {
ll a = val, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
return modint61(u);
}
modint61 pow(ll n) const {
assert(n >= 0);
modint61 ret(1), mul(val);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul, n >>= 1;
}
return ret;
}
};
#ifdef FASTIO
void rd(modint61 &x) {
fastio::rd(x.val);
assert(0 <= x.val && x.val < modint61::mod);
}
void wt(modint61 x) { fastio::wt(x.val); }
#endif
#line 1 "linalg/matrix_rank.hpp"
template <typename T>
int matrix_rank(vc<vc<T>> a, int n = -1, int m = -1) {
if (n == 0) return 0;
if (n == -1) { n = len(a), m = len(a[0]); }
assert(n == len(a) && m == len(a[0]));
int rk = 0;
FOR(j, m) {
if (rk == n) break;
if (a[rk][j] == 0) {
FOR(i, rk + 1, n) if (a[i][j] != T(0)) {
swap(a[rk], a[i]);
break;
}
}
if (a[rk][j] == 0) continue;
T c = T(1) / a[rk][j];
FOR(k, j, m) a[rk][k] *= c;
FOR(i, rk + 1, n) {
T c = a[i][j];
FOR3(k, j, m) { a[i][k] -= a[rk][k] * c; }
}
++rk;
}
return rk;
}
#line 4 "graph/maximum_matching_size.hpp"
template <typename GT>
int maximum_matching_size(GT& G) {
static_assert(!GT::is_directed);
using mint = modint61;
int N = G.N;
vv(mint, tutte, N, N);
for (auto&& e: G.edges) {
mint x = RNG(mint::get_mod());
int i = e.frm, j = e.to;
tutte[i][j] += x;
tutte[j][i] -= x;
}
return matrix_rank(tutte, N, N) / 2;
}