cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: graph/test/chromatic_number.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number"
#include "../chromatic_number.hpp"
#include "../../number/factorize.hpp"
#include "../../number/modint_runtime.hpp"
#include "../../random/rand_nondeterministic.hpp"

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> to(N);

    long long md = 4;
    do { md = rnd(1LL << 29, 1LL << 30); } while (!is_prime(md));
    cerr << md << '\n';
    ModIntRuntime::set_mod(md);

    while (M--) {
        int u, v;
        cin >> u >> v;
        to[u] |= 1 << v;
        to[v] |= 1 << u;
    }
    cout << ChromaticNumber<ModIntRuntime>(to) << '\n';
}
#line 1 "graph/test/chromatic_number.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/chromatic_number"
#line 2 "graph/chromatic_number.hpp"
#include <numeric>
#include <vector>

// CUT begin
// (vertex) chromatic number: （頂点）彩色数
// Verified: https://judge.yosupo.jp/problem/chromatic_number, https://atcoder.jp/contests/abc187/tasks/abc187_f
// Reference:
// [1] A. Bjorklund and T. Husfeldt, "Inclusion--Exclusion Algorithms for Counting Set Partitions,"
//     2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06).
// - https://www.slideshare.net/wata_orz/ss-12131479
template <typename MODINT, typename Int> int ChromaticNumber(const std::vector<Int> &edge) {
    const int V = edge.size(), S = 1 << V;
    if (V == 0) return 0;
    std::vector<MODINT> f(S), g(S);
    for (int s = 0; s < S; s++) g[s] = (__builtin_popcount(s) & 1) ? 1 : -1;
    f[0] = 1;
    for (int s = 1; s < S; s++) {
        int i = __builtin_ctz(s);
        f[s] = f[s - (1 << i)] + f[(s - (1 << i)) & ~edge[i]];
    }
    for (int k = 1; k < V; k++) {
        for (int s = 0; s < S; s++) g[s] *= f[s];
        if (std::accumulate(g.begin(), g.end(), MODINT()).val()) return k;
    }
    return V;
};
#line 2 "random/xorshift.hpp"
#include <cstdint>

// CUT begin
uint32_t rand_int() // XorShift random integer generator
{
    static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    uint32_t t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
double rand_double() { return (double)rand_int() / UINT32_MAX; }
#line 3 "number/factorize.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#line 8 "number/factorize.hpp"

namespace SPRP {
// http://miller-rabin.appspot.com/
const std::vector<std::vector<__int128>> bases{
    {126401071349994536},                              // < 291831
    {336781006125, 9639812373923155},                  // < 1050535501 (1e9)
    {2, 2570940, 211991001, 3749873356},               // < 47636622961201 (4e13)
    {2, 325, 9375, 28178, 450775, 9780504, 1795265022} // <= 2^64
};
inline int get_id(long long n) {
    if (n < 291831) {
        return 0;
    } else if (n < 1050535501) {
        return 1;
    } else if (n < 47636622961201)
        return 2;
    else { return 3; }
}
} // namespace SPRP

// Miller-Rabin primality test
// https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
// Complexity: O(lg n) per query
struct {
    long long modpow(__int128 x, __int128 n, long long mod) noexcept {
        __int128 ret = 1;
        for (x %= mod; n; x = x * x % mod, n >>= 1) ret = (n & 1) ? ret * x % mod : ret;
        return ret;
    }
    bool operator()(long long n) noexcept {
        if (n < 2) return false;
        if (n % 2 == 0) return n == 2;
        int s = __builtin_ctzll(n - 1);

        for (__int128 a : SPRP::bases[SPRP::get_id(n)]) {
            if (a % n == 0) continue;
            a = modpow(a, (n - 1) >> s, n);
            bool may_composite = true;
            if (a == 1) continue;
            for (int r = s; r--; a = a * a % n) {
                if (a == n - 1) may_composite = false;
            }
            if (may_composite) return false;
        }
        return true;
    }
} is_prime;

struct {
    // Pollard's rho algorithm: find factor greater than 1
    long long find_factor(long long n) {
        assert(n > 1);
        if (n % 2 == 0) return 2;
        if (is_prime(n)) return n;
        long long c = 1;
        auto f = [&](__int128 x) -> long long { return (x * x + c) % n; };

        for (int t = 1;; t++) {
            for (c = 0; c == 0 or c + 2 == n;) c = rand_int() % n;
            long long x0 = t, m = std::max(n >> 3, 1LL), x, ys, y = x0, r = 1, g, q = 1;
            do {
                x = y;
                for (int i = r; i--;) y = f(y);
                long long k = 0;
                do {
                    ys = y;
                    for (int i = std::min(m, r - k); i--;)
                        y = f(y), q = __int128(q) * std::abs(x - y) % n;
                    g = std::__gcd<long long>(q, n);
                    k += m;
                } while (k < r and g <= 1);
                r <<= 1;
            } while (g <= 1);
            if (g == n) {
                do {
                    ys = f(ys);
                    g = std::__gcd(std::abs(x - ys), n);
                } while (g <= 1);
            }
            if (g != n) return g;
        }
    }

    std::vector<long long> operator()(long long n) {
        std::vector<long long> ret;
        while (n > 1) {
            long long f = find_factor(n);
            if (f < n) {
                auto tmp = operator()(f);
                ret.insert(ret.end(), tmp.begin(), tmp.end());
            } else
                ret.push_back(n);
            n /= f;
        }
        std::sort(ret.begin(), ret.end());
        return ret;
    }
    long long euler_phi(long long n) {
        long long ret = 1, last = -1;
        for (auto p : this->operator()(n)) ret *= p - (last != p), last = p;
        return ret;
    }
} FactorizeLonglong;
#line 2 "number/modint_runtime.hpp"
#include <iostream>
#include <set>
#line 5 "number/modint_runtime.hpp"

struct ModIntRuntime {
private:
    static int md;

public:
    using lint = long long;
    static int mod() { return md; }
    int val_;
    static std::vector<ModIntRuntime> &facs() {
        static std::vector<ModIntRuntime> facs_;
        return facs_;
    }
    static int &get_primitive_root() {
        static int primitive_root_ = 0;
        if (!primitive_root_) {
            primitive_root_ = [&]() {
                std::set<int> fac;
                int v = md - 1;
                for (lint i = 2; i * i <= v; i++)
                    while (v % i == 0) fac.insert(i), v /= i;
                if (v > 1) fac.insert(v);
                for (int g = 1; g < md; g++) {
                    bool ok = true;
                    for (auto i : fac)
                        if (ModIntRuntime(g).power((md - 1) / i) == 1) {
                            ok = false;
                            break;
                        }
                    if (ok) return g;
                }
                return -1;
            }();
        }
        return primitive_root_;
    }
    static void set_mod(const int &m) {
        if (md != m) facs().clear();
        md = m;
        get_primitive_root() = 0;
    }
    ModIntRuntime &_setval(lint v) {
        val_ = (v >= md ? v - md : v);
        return *this;
    }
    int val() const noexcept { return val_; }
    ModIntRuntime() : val_(0) {}
    ModIntRuntime(lint v) { _setval(v % md + md); }
    explicit operator bool() const { return val_ != 0; }
    ModIntRuntime operator+(const ModIntRuntime &x) const {
        return ModIntRuntime()._setval((lint)val_ + x.val_);
    }
    ModIntRuntime operator-(const ModIntRuntime &x) const {
        return ModIntRuntime()._setval((lint)val_ - x.val_ + md);
    }
    ModIntRuntime operator*(const ModIntRuntime &x) const {
        return ModIntRuntime()._setval((lint)val_ * x.val_ % md);
    }
    ModIntRuntime operator/(const ModIntRuntime &x) const {
        return ModIntRuntime()._setval((lint)val_ * x.inv().val() % md);
    }
    ModIntRuntime operator-() const { return ModIntRuntime()._setval(md - val_); }
    ModIntRuntime &operator+=(const ModIntRuntime &x) { return *this = *this + x; }
    ModIntRuntime &operator-=(const ModIntRuntime &x) { return *this = *this - x; }
    ModIntRuntime &operator*=(const ModIntRuntime &x) { return *this = *this * x; }
    ModIntRuntime &operator/=(const ModIntRuntime &x) { return *this = *this / x; }
    friend ModIntRuntime operator+(lint a, const ModIntRuntime &x) {
        return ModIntRuntime()._setval(a % md + x.val_);
    }
    friend ModIntRuntime operator-(lint a, const ModIntRuntime &x) {
        return ModIntRuntime()._setval(a % md - x.val_ + md);
    }
    friend ModIntRuntime operator*(lint a, const ModIntRuntime &x) {
        return ModIntRuntime()._setval(a % md * x.val_ % md);
    }
    friend ModIntRuntime operator/(lint a, const ModIntRuntime &x) {
        return ModIntRuntime()._setval(a % md * x.inv().val() % md);
    }
    bool operator==(const ModIntRuntime &x) const { return val_ == x.val_; }
    bool operator!=(const ModIntRuntime &x) const { return val_ != x.val_; }
    bool operator<(const ModIntRuntime &x) const {
        return val_ < x.val_;
    } // To use std::map<ModIntRuntime, T>
    friend std::istream &operator>>(std::istream &is, ModIntRuntime &x) {
        lint t;
        return is >> t, x = ModIntRuntime(t), is;
    }
    friend std::ostream &operator<<(std::ostream &os, const ModIntRuntime &x) {
        return os << x.val_;
    }

    lint power(lint n) const {
        lint ans = 1, tmp = this->val_;
        while (n) {
            if (n & 1) ans = ans * tmp % md;
            tmp = tmp * tmp % md;
            n /= 2;
        }
        return ans;
    }
    ModIntRuntime pow(lint n) const { return power(n); }
    ModIntRuntime inv() const { return this->pow(md - 2); }

    ModIntRuntime fac() const {
        int l0 = facs().size();
        if (l0 > this->val_) return facs()[this->val_];

        facs().resize(this->val_ + 1);
        for (int i = l0; i <= this->val_; i++)
            facs()[i] = (i == 0 ? ModIntRuntime(1) : facs()[i - 1] * ModIntRuntime(i));
        return facs()[this->val_];
    }

    ModIntRuntime doublefac() const {
        lint k = (this->val_ + 1) / 2;
        return (this->val_ & 1)
                   ? ModIntRuntime(k * 2).fac() / (ModIntRuntime(2).pow(k) * ModIntRuntime(k).fac())
                   : ModIntRuntime(k).fac() * ModIntRuntime(2).pow(k);
    }

    ModIntRuntime nCr(int r) const {
        if (r < 0 or this->val_ < r) return ModIntRuntime(0);
        return this->fac() / ((*this - r).fac() * ModIntRuntime(r).fac());
    }

    ModIntRuntime sqrt() const {
        if (val_ == 0) return 0;
        if (md == 2) return val_;
        if (power((md - 1) / 2) != 1) return 0;
        ModIntRuntime b = 1;
        while (b.power((md - 1) / 2) == 1) b += 1;
        int e = 0, m = md - 1;
        while (m % 2 == 0) m >>= 1, e++;
        ModIntRuntime x = power((m - 1) / 2), y = (*this) * x * x;
        x *= (*this);
        ModIntRuntime z = b.power(m);
        while (y != 1) {
            int j = 0;
            ModIntRuntime t = y;
            while (t != 1) j++, t *= t;
            z = z.power(1LL << (e - j - 1));
            x *= z, z *= z, y *= z;
            e = j;
        }
        return ModIntRuntime(std::min(x.val_, md - x.val_));
    }
};
int ModIntRuntime::md = 1;
#line 2 "random/rand_nondeterministic.hpp"
#include <chrono>
#include <random>

struct rand_int_ {
    using lint = long long;
    std::mt19937 mt;
    rand_int_() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    lint operator()(lint x) { return this->operator()(0, x); } // [0, x)
    lint operator()(lint l, lint r) {
        std::uniform_int_distribution<lint> d(l, r - 1);
        return d(mt);
    }
} rnd;
#line 6 "graph/test/chromatic_number.test.cpp"

#line 9 "graph/test/chromatic_number.test.cpp"
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> to(N);

    long long md = 4;
    do { md = rnd(1LL << 29, 1LL << 30); } while (!is_prime(md));
    cerr << md << '\n';
    ModIntRuntime::set_mod(md);

    while (M--) {
        int u, v;
        cin >> u >> v;
        to[u] |= 1 << v;
        to[v] |= 1 << u;
    }
    cout << ChromaticNumber<ModIntRuntime>(to) << '\n';
}
Back to top page