cpp_src/graph/helper/EdgeCount.hpp

View this file on GitHub
Last update: 2022-01-02 16:22:57+09:00
Include: #include "cpp_src/graph/helper/EdgeCount.hpp"

Code

// ABC213G (also subset convolution)
// O(N * 2^N)
// es[S] := #((u,v) s.t. u \in S & v \in S)

V<int> edge_count(const VV<int>& e) {
    int n = SZ(e);
    V<int> es(1 << n);
    rep(i, 1 << n) {
        if (i == 0) continue;
        int p = -1;

        rep(j, n) if (i >> j & 1) { p = j; }
        es[i] = es[i ^ (1 << p)];
        rep(j, p) if (i >> j & 1) { es[i] += e[j][p]; }
    }
    return es;
}

#line 1 "cpp_src/graph/helper/EdgeCount.hpp"
// ABC213G (also subset convolution)
// O(N * 2^N)
// es[S] := #((u,v) s.t. u \in S & v \in S)

V<int> edge_count(const VV<int>& e) {
    int n = SZ(e);
    V<int> es(1 << n);
    rep(i, 1 << n) {
        if (i == 0) continue;
        int p = -1;

        rep(j, n) if (i >> j & 1) { p = j; }
        es[i] = es[i ^ (1 << p)];
        rep(j, p) if (i >> j & 1) { es[i] += e[j][p]; }
    }
    return es;
}