graph/chromatic.hpp

• View this file on GitHub
• Last update: 2023-11-02 05:00:07+09:00
• Include: #include "graph/chromatic.hpp"

Depends on

• mod/mongomery_modint.hpp
• nt/primetest.hpp
• random/base.hpp

Verified with

• test/library_checker/graph/chromatic_number.test.cpp

Code

#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;
}

Back to top page