This documentation is automatically generated by online-judge-tools/verification-helper
#include "graph/chromatic.hpp"
#include "random/base.hpp"
#include "nt/primetest.hpp"
// O(N2^N)
template <typename Graph, int TRIAL = 0>
int chromatic_number(Graph& G) {
assert(G.is_prepared());
int N = G.N;
vc<int> nbd(N);
FOR(v, N) for (auto&& e: G[v]) nbd[v] |= 1 << e.to;
// s の subset であるような独立集合の数え上げ
vc<int> dp(1 << N);
dp[0] = 1;
FOR(v, N) FOR(s, 1 << v) { dp[s | 1 << v] = dp[s] + dp[s & (~nbd[v])]; }
vi pow(1 << N);
auto solve_p = [&](int p) -> int {
FOR(s, 1 << N) pow[s] = ((N - popcnt(s)) & 1 ? 1 : -1);
FOR(k, 1, N) {
ll sum = 0;
FOR(s, 1 << N) {
pow[s] = pow[s] * dp[s];
if (p) pow[s] %= p;
sum += pow[s];
}
if (p) sum %= p;
if (sum != 0) { return k; }
}
return N;
};
int ANS = 0;
chmax(ANS, solve_p(0));
FOR(TRIAL) {
int p;
while (1) {
p = RNG(1LL << 30, 1LL << 31);
if (primetest(p)) break;
}
chmax(ANS, solve_p(p));
}
return ANS;
}
#line 2 "random/base.hpp"
u64 RNG_64() {
static uint64_t x_
= uint64_t(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/mongomery_modint.hpp"
// odd mod.
// x の代わりに rx を持つ
template <int id, typename U1, typename U2>
struct Mongomery_modint {
using mint = Mongomery_modint;
inline static U1 m, r, n2;
static constexpr int W = numeric_limits<U1>::digits;
static void set_mod(U1 mod) {
assert(mod & 1 && mod <= U1(1) << (W - 2));
m = mod, n2 = -U2(m) % m, r = m;
FOR(5) r *= 2 - m * r;
r = -r;
assert(r * m == U1(-1));
}
static U1 reduce(U2 b) { return (b + U2(U1(b) * r) * m) >> W; }
U1 x;
Mongomery_modint() : x(0) {}
Mongomery_modint(U1 x) : x(reduce(U2(x) * n2)){};
U1 val() const {
U1 y = reduce(x);
return y >= m ? y - m : y;
}
mint &operator+=(mint y) {
x = ((x += y.x) >= m ? x - m : x);
return *this;
}
mint &operator-=(mint y) {
x -= (x >= y.x ? y.x : y.x - m);
return *this;
}
mint &operator*=(mint y) {
x = reduce(U2(x) * y.x);
return *this;
}
mint operator+(mint y) const { return mint(*this) += y; }
mint operator-(mint y) const { return mint(*this) -= y; }
mint operator*(mint y) const { return mint(*this) *= y; }
bool operator==(mint y) const {
return (x >= m ? x - m : x) == (y.x >= m ? y.x - m : y.x);
}
bool operator!=(mint y) const { return not operator==(y); }
mint pow(ll n) const {
assert(n >= 0);
mint y = 1, z = *this;
for (; n; n >>= 1, z *= z)
if (n & 1) y *= z;
return y;
}
};
template <int id>
using Mongomery_modint_32 = Mongomery_modint<id, u32, u64>;
template <int id>
using Mongomery_modint_64 = Mongomery_modint<id, u64, u128>;
#line 3 "nt/primetest.hpp"
bool primetest(const u64 x) {
assert(x < u64(1) << 62);
if (x == 2 or x == 3 or x == 5 or x == 7) return true;
if (x % 2 == 0 or x % 3 == 0 or x % 5 == 0 or x % 7 == 0) return false;
if (x < 121) return x > 1;
const u64 d = (x - 1) >> lowbit(x - 1);
using mint = Mongomery_modint_64<202311020>;
mint::set_mod(x);
const mint one(u64(1)), minus_one(x - 1);
auto ok = [&](u64 a) -> bool {
auto y = mint(a).pow(d);
u64 t = d;
while (y != one && y != minus_one && t != x - 1) y *= y, t <<= 1;
if (y != minus_one && t % 2 == 0) return false;
return true;
};
if (x < (u64(1) << 32)) {
for (u64 a: {2, 7, 61})
if (!ok(a)) return false;
} else {
for (u64 a: {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
if (!ok(a)) return false;
}
}
return true;
}
#line 3 "graph/chromatic.hpp"
// O(N2^N)
template <typename Graph, int TRIAL = 0>
int chromatic_number(Graph& G) {
assert(G.is_prepared());
int N = G.N;
vc<int> nbd(N);
FOR(v, N) for (auto&& e: G[v]) nbd[v] |= 1 << e.to;
// s の subset であるような独立集合の数え上げ
vc<int> dp(1 << N);
dp[0] = 1;
FOR(v, N) FOR(s, 1 << v) { dp[s | 1 << v] = dp[s] + dp[s & (~nbd[v])]; }
vi pow(1 << N);
auto solve_p = [&](int p) -> int {
FOR(s, 1 << N) pow[s] = ((N - popcnt(s)) & 1 ? 1 : -1);
FOR(k, 1, N) {
ll sum = 0;
FOR(s, 1 << N) {
pow[s] = pow[s] * dp[s];
if (p) pow[s] %= p;
sum += pow[s];
}
if (p) sum %= p;
if (sum != 0) { return k; }
}
return N;
};
int ANS = 0;
chmax(ANS, solve_p(0));
FOR(TRIAL) {
int p;
while (1) {
p = RNG(1LL << 30, 1LL << 31);
if (primetest(p)) break;
}
chmax(ANS, solve_p(p));
}
return ANS;
}