noya2_Library

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

View the Project on GitHub noya2ruler/noya2_Library

:heavy_check_mark: math/euler_circuit_counting.hpp

Depends on

Verified with

Code

#pragma once

#include"../math/spanning_tree_counting.hpp"
#include"../math/binomial.hpp"

namespace noya2 {

// BEST theorem
// https://en.wikipedia.org/wiki/BEST_theorem
template<typename T>
T euler_circuit_counting(int n, const std::vector<std::tuple<int, int, long long>> &es){
    // i_deg == o_deg
    std::vector<long long> deg(n,0);
    for (auto [u, v, c] : es){
        deg[u] -= c;
        deg[v] += c;
    }
    for (int i = 0; i < n; i++) if (deg[i] != 0) return T(0);
    // edges are connected
    int m = es.size();
    std::vector<bool> vis(n,false);
    std::vector<std::vector<int>> g(n);
    for (auto [u, v, c] : es){
        if (c == 0) continue;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    for (int s = 0; s < n; s++){
        if (g[s].empty()) continue;
        std::queue<int> que;
        que.push(s);
        vis[s] = true;
        while (!que.empty()){
            int v = que.front(); que.pop();
            for (int u : g[v]){
                if (!vis[u]){
                    vis[u] = true;
                    que.push(u);
                }
            }
        }
        break;
    }
    for (auto [u, v, c] : es){
        if (!vis[u]) return T(0);
    }
    // directed spanning tree counting
    std::vector<int> ids(n);
    int nonzero = 0;
    for (int v = 0; v < n; v++){
        if (!g[v].empty()){
            ids[v] = nonzero++;
        }
    }
    std::vector<std::tuple<int, int, T>> nes(m);
    for (int i = 0; i < m; i++){
        auto [u, v, c] = es[i];
        nes[i] = {ids[u],ids[v],c};
        deg[v] += c;
    }
    binomial<T> bnm;
    T ans = directed_spanning_tree_counting(nonzero,nes);
    for (int i = 0; i < n; i++){
        if (deg[i] > 0){
            ans *= bnm.fact(deg[i]-1);
        }
    }
    return ans;
}

} // namespace noya2
#line 2 "math/euler_circuit_counting.hpp"

#line 2 "math/spanning_tree_counting.hpp"

#line 2 "math/matrix.hpp"

#include <vector>
#include <array>
#include <iostream>
#include <ranges>
#include <cassert>

namespace noya2 {

template<typename T, size_t hw = -1uz>
struct matrix {
    static constexpr int h = hw, w = hw;
    std::array<T, hw*hw> m;
    matrix () : m({}) {}
    matrix (const std::array<T, hw*hw> &_m) : m(_m) {}
    matrix (const std::array<std::array<T, hw>, hw> &_m){
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
            m[idx(i,j)] = _m[i][j];
        }
    }
    matrix (const std::vector<std::vector<T>> &_m){
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
            m[idx(i,j)] = _m[i][j];
        }
    }
    auto operator[](int i) const {
        return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
    }
    auto operator[](int i){
        return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
    }
    matrix &operator+= (const matrix &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] += r.m[idx(i,j)];
            }
        }
        return *this;
    }
    matrix &operator-= (const matrix &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] -= r.m[idx(i,j)];
            }
        }
        return *this;
    }
    matrix &operator*= (const matrix &r){
        matrix ret;
        for (int i = 0; i < h; i++){
            for (int k = 0; k < w; k++){
                for (int j = 0; j < r.w; j++){
                    ret.m[idx(i,j)] += m[idx(i,k)] * r.m[idx(k,j)];
                }
            }
        }
        return *this = ret;
    }
    matrix operator+ (const matrix &r) const { return matrix(*this) += r; }
    matrix operator- (const matrix &r) const { return matrix(*this) -= r; }
    matrix operator* (const matrix &r) const { return matrix(*this) *= r; }
    matrix& operator*=(const T &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] *= r;
            }
        }
        return *this;
    }
    friend matrix operator* (const T &r, const matrix &mat){
        return matrix(mat) *= r;
    }
    friend matrix operator* (const matrix &mat, const T &r){
        return matrix(mat) *= r;
    }
    matrix pow(long long n){
        if (n == 0) return e();
        matrix f = pow(n / 2);
        matrix ret = f * f;
        if (n & 1) ret *= (*this);
        return ret;
    }
    int idx(int i, int j){
        return i * w + j;
    }
    static matrix e(){
        matrix ret;
        for (int i = 0; i < h; i++){
            ret[i][i] = T(1);
        }
        return ret;
    }
    friend std::ostream &operator<<(std::ostream &os, const matrix &mat){
        for (int i = 0; i < mat.h; i++){
            if (i != 0) os << '\n';
            for (int j = 0; j < mat.w; j++){
                if (j != 0) os << ' ';
                os << mat[i][j];
            }
        }
        return os;
    }
    friend std::istream &operator>>(std::istream &is, matrix &mat){
        for (int i = 0; i < mat.h; i++){
            for (int j = 0; j < mat.w; j++){
                is >> mat[i][j];
            }
        }
        return is;
    }
    friend bool operator==(const matrix &a, const matrix &b){
        for (int i = 0; i < a.h; i++){
            for (int j = 0; j < a.w; j++){
                if (a[i][j] != b[i][j]){
                    return false;
                }
            }
        }
        return true;
    }
};

template<typename T>
struct matrix<T,-1uz> {
    int h, w;
    std::vector<T> m;
    matrix () {}
    matrix (int _h) : matrix(_h,_h) {}
    matrix (int _h, int _w) : h(_h), w(_w), m(_h*_w) {}
    matrix (int _h, int _w, const std::vector<T> &_m) : h(_h), w(_w), m(_m) {
        assert((int)_m.size() == _h*_w);
    }
    matrix (const std::vector<std::vector<T>> &_m){
        h = _m.size();
        assert(h >= 1);
        w = _m[0].size();
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
            m[idx(i,j)] = _m[i][j];
        }
    }
    auto operator[](int i) const {
        return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
    }
    auto operator[](int i){
        return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
    }
    matrix &operator+= (const matrix &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] += r.m[idx(i,j)];
            }
        }
        return *this;
    }
    matrix &operator-= (const matrix &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] -= r.m[idx(i,j)];
            }
        }
        return *this;
    }
    matrix &operator*= (const matrix &r){
        matrix ret(h, r.w);
        for (int i = 0; i < h; i++){
            for (int k = 0; k < w; k++){
                for (int j = 0; j < r.w; j++){
                    ret.m[idx(i,j)] += m[idx(i,k)] * r.m[idx(k,j)];
                }
            }
        }
        return *this = ret;
    }
    matrix operator+ (const matrix &r) const { return matrix(*this) += r; }
    matrix operator- (const matrix &r) const { return matrix(*this) -= r; }
    matrix operator* (const matrix &r) const { return matrix(*this) *= r; }
    matrix& operator*=(const T &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] *= r;
            }
        }
        return *this;
    }
    friend matrix operator* (const T &r, const matrix &mat){
        return matrix(mat) *= r;
    }
    friend matrix operator* (const matrix &mat, const T &r){
        return matrix(mat) *= r;
    }
    matrix pow(long long n){
        if (n == 0) return e(h);
        matrix f = pow(n / 2);
        matrix ret = f * f;
        if (n & 1) ret *= (*this);
        return ret;
    }
    int idx(int i, int j){
        return i * w + j;
    }
    static matrix e(int _h){
        auto ret = matrix(_h, _h);
        for (int i = 0; i < _h; i++){
            ret[i][i] = T(1);
        }
        return ret;
    }
    friend std::ostream &operator<<(std::ostream &os, const matrix &mat){
        for (int i = 0; i < mat.h; i++){
            if (i != 0) os << '\n';
            for (int j = 0; j < mat.w; j++){
                if (j != 0) os << ' ';
                os << mat[i][j];
            }
        }
        return os;
    }
    friend std::istream &operator>>(std::istream &is, matrix &mat){
        for (int i = 0; i < mat.h; i++){
            for (int j = 0; j < mat.w; j++){
                is >> mat[i][j];
            }
        }
        return is;
    }
};

template<typename T, size_t _hw = -1uz>
T determinant(matrix<T, _hw> mat){
    int hw = mat.h;
    T ret = 1;
    for (int i = 0; i < hw; i++) {
        int idx = -1;
        for (int j = i; j < hw; j++) {
            if (mat[j][i] != 0) {
                idx = j;
                break;
            }
        }
        if (idx == -1) return 0;
        if (i != idx) {
            ret *= T(-1);
            for (int j = 0; j < hw; j++){
                std::swap(mat[i][j],mat[idx][j]);
            }
        }
        ret *= mat[i][i];
        T inv = T(1) / mat[i][i];
        for (int j = 0; j < hw; j++) {
            mat[i][j] *= inv;
        }
        for (int j = i + 1; j < hw; j++) {
            T a = mat[j][i];
            if (a == 0) continue;
            for (int k = i; k < hw; k++) {
                mat[j][k] -= mat[i][k] * a;
            }
        }
    }
    return ret;
}

} // namespace noya2
#line 4 "math/spanning_tree_counting.hpp"

namespace noya2 {

template<typename T>
T directed_spanning_tree_counting(int n, const std::vector<std::tuple<int,int,T>> &es){
    matrix<T> mat(n-1,n-1);
    for (auto [u, v, c] : es){
        if (u < n-1 && v < n-1){
            mat[u][v] -= c;
        }
        if (v < n-1){
            mat[v][v] += c;
        }
    }
    return determinant(mat);
}

template<typename T>
T undirected_spanning_tree_counting(int n, const std::vector<std::tuple<int,int,T>> &es){
    matrix<T> mat(n-1,n-1);
    for (auto [u, v, c] : es){
        if (u < n-1 && v < n-1){
            mat[u][v] -= c;
            mat[v][u] -= c;
        }
        if (v < n-1){
            mat[v][v] += c;
        }
        if (u < n-1){
            mat[u][u] += c;
        }
    }
    return determinant(mat);
}

} // namespace noya2
#line 2 "math/binomial.hpp"

#line 4 "math/binomial.hpp"
namespace noya2 {

template<typename mint>
struct binomial {
    binomial(int len = 300000){ extend(len); }
    static mint fact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _fact[n];
    }
    static mint ifact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _ifact[n];
    }
    static mint inv(int n){
        return ifact(n) * fact(n-1);
    }
    static mint C(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(r) * ifact(n-r);
    }
    static mint P(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(n-r);
    }
    static mint catalan(int n){
        return C(n * 2, n) * inv(n + 1);
    }
    inline mint operator()(int n, int r) { return C(n, r); }
    template<class... Cnts>
    static mint M(const Cnts&... cnts){
        return multinomial(0,1,cnts...);
    }
    static void initialize(int len = 2){
        _fact.clear();
        _ifact.clear();
        extend(len);
    }
  private:
    static mint multinomial(const int& sum, const mint& div_prod){
        if (sum < 0) return 0;
        return fact(sum) * div_prod;
    }
    template<class... Tail>
    static mint multinomial(const int& sum, const mint& div_prod, const int& n1, const Tail&... tail){
        if (n1 < 0) return 0;
        return multinomial(sum+n1,div_prod*ifact(n1),tail...);
    }
    static inline std::vector<mint> _fact, _ifact;
    static void extend(int len = -1){
        if (_fact.empty()){
            _fact = _ifact = {1,1};
        }
        int siz = _fact.size();
        if (len == -1) len = siz * 2;
        len = (int)min<long long>(len, mint::mod() - 1);
        if (len < siz) return ;
        _fact.resize(len+1), _ifact.resize(len+1);
        for (int i = siz; i <= len; i++) _fact[i] = _fact[i-1] * i;
        _ifact[len] = _fact[len].inv();
        for (int i = len; i > siz; i--) _ifact[i-1] = _ifact[i] * i;
    }
};

} // namespace noya2
#line 5 "math/euler_circuit_counting.hpp"

namespace noya2 {

// BEST theorem
// https://en.wikipedia.org/wiki/BEST_theorem
template<typename T>
T euler_circuit_counting(int n, const std::vector<std::tuple<int, int, long long>> &es){
    // i_deg == o_deg
    std::vector<long long> deg(n,0);
    for (auto [u, v, c] : es){
        deg[u] -= c;
        deg[v] += c;
    }
    for (int i = 0; i < n; i++) if (deg[i] != 0) return T(0);
    // edges are connected
    int m = es.size();
    std::vector<bool> vis(n,false);
    std::vector<std::vector<int>> g(n);
    for (auto [u, v, c] : es){
        if (c == 0) continue;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    for (int s = 0; s < n; s++){
        if (g[s].empty()) continue;
        std::queue<int> que;
        que.push(s);
        vis[s] = true;
        while (!que.empty()){
            int v = que.front(); que.pop();
            for (int u : g[v]){
                if (!vis[u]){
                    vis[u] = true;
                    que.push(u);
                }
            }
        }
        break;
    }
    for (auto [u, v, c] : es){
        if (!vis[u]) return T(0);
    }
    // directed spanning tree counting
    std::vector<int> ids(n);
    int nonzero = 0;
    for (int v = 0; v < n; v++){
        if (!g[v].empty()){
            ids[v] = nonzero++;
        }
    }
    std::vector<std::tuple<int, int, T>> nes(m);
    for (int i = 0; i < m; i++){
        auto [u, v, c] = es[i];
        nes[i] = {ids[u],ids[v],c};
        deg[v] += c;
    }
    binomial<T> bnm;
    T ans = directed_spanning_tree_counting(nonzero,nes);
    for (int i = 0; i < n; i++){
        if (deg[i] > 0){
            ans *= bnm.fact(deg[i]-1);
        }
    }
    return ans;
}

} // namespace noya2
Back to top page