結果

問題 No.2507 Yet Another Subgraph Counting
ユーザー suisensuisen
提出日時 2023-08-21 23:21:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 270 ms / 2,000 ms
コード長 8,768 bytes
コンパイル時間 1,475 ms
コンパイル使用メモリ 90,296 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 14:15:39
合計ジャッジ時間 6,296 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 11 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 11 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 10 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 11 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 11 ms
5,376 KB
testcase_24 AC 3 ms
5,376 KB
testcase_25 AC 28 ms
5,376 KB
testcase_26 AC 86 ms
5,376 KB
testcase_27 AC 10 ms
5,376 KB
testcase_28 AC 29 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 86 ms
5,376 KB
testcase_31 AC 265 ms
5,376 KB
testcase_32 AC 265 ms
5,376 KB
testcase_33 AC 10 ms
5,376 KB
testcase_34 AC 5 ms
5,376 KB
testcase_35 AC 10 ms
5,376 KB
testcase_36 AC 3 ms
5,376 KB
testcase_37 AC 266 ms
5,376 KB
testcase_38 AC 270 ms
5,376 KB
testcase_39 AC 265 ms
5,376 KB
testcase_40 AC 266 ms
5,376 KB
testcase_41 AC 269 ms
5,376 KB
testcase_42 AC 268 ms
5,376 KB
testcase_43 AC 85 ms
5,376 KB
testcase_44 AC 265 ms
5,376 KB
testcase_45 AC 10 ms
5,376 KB
testcase_46 AC 11 ms
5,376 KB
testcase_47 AC 265 ms
5,376 KB
testcase_48 AC 3 ms
5,376 KB
testcase_49 AC 264 ms
5,376 KB
testcase_50 AC 5 ms
5,376 KB
testcase_51 AC 85 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

namespace library {
    namespace bits {
        template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
        size_t bit_width(const T v) {
            size_t res = 0;
            while (T{1} << res <= v) ++res;
            return res;
        }
        template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
        T bit_deposite(const T src, const T mask, const size_t bitwidth) {
            T dst = 0;
            size_t j = 0;
            for (size_t i = 0; i < bitwidth; ++i) {
                if ((mask >> i) & 1) dst |= ((src >> j) & 1) << i, ++j;
            }
            return dst;
        }
        template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
        size_t popcount(const T v) {
            if constexpr (std::numeric_limits<std::make_unsigned_t<T>>::digits <= 32) {
                return __builtin_popcount(v);
            } else {
                return __builtin_popcountll(v);
            }
        }
        template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
        size_t count_tz(const T v) {
            if constexpr (std::numeric_limits<std::make_unsigned_t<T>>::digits <= 32) {
                return __builtin_ctz(v);
            } else {
                return __builtin_ctzll(v);
            }
        }
    }
    
    namespace kronecker_power_transform {
        namespace details {
            template <auto transform, typename RefGettter, size_t... I>
            void unit_transform(RefGettter ref, std::index_sequence<I...>) {
                transform(ref(I)...);
            }
        }
        template <typename T, size_t D, auto unit_transform>
        void kronecker_power_transform(std::vector<T> &x) {
            const size_t n = x.size();
            for (size_t block = 1; block < n; block *= D) {
                for (size_t l = 0; l < n; l += D * block) {
                    for (size_t offset = l; offset < l + block; ++offset) {
                        const auto ref = [&](size_t i) -> T& { return x[offset + i * block]; };
                        details::unit_transform<unit_transform>(ref, std::make_index_sequence<D>{});
                    }
                }
            }
        }
    }
    
    namespace subset_transform {
        namespace details {
            template <typename T> void zeta_unit(T &x0, T &x1) { x1 += x0; }
            template <typename T> void mobius_unit(T &x0, T &x1) { x1 -= x0; }
        }
        template <typename T>
        void zeta(std::vector<T> &a) {
            kronecker_power_transform::kronecker_power_transform<T, 2, details::zeta_unit<T>>(a);
        }
        template <typename T>
        void mobius(std::vector<T> &a) {
            kronecker_power_transform::kronecker_power_transform<T, 2, details::mobius_unit<T>>(a);
        }
    }
    
    namespace set_power_series {
        namespace details {
            template <typename T>
            struct polynomial : std::vector<T> {
                using std::vector<T>::vector;
                polynomial& operator+=(const polynomial &q) {
                    assert(this->size() == q.size());
                    for (size_t i = 0; i < q.size(); ++i) (*this)[i] += q[i];
                    return *this;
                }
                polynomial& operator-=(const polynomial &q) {
                    assert(this->size() == q.size());
                    for (size_t i = 0; i < q.size(); ++i) (*this)[i] -= q[i];
                    return *this;
                }
                polynomial& operator*=(const polynomial &q) {
                    const size_t n = this->size();
                    assert(n == q.size());
                    polynomial r(n);
                    for (size_t i = 0; i < n; ++i) for (size_t j = 0; i + j < n; ++j) r[i + j] += (*this)[i] * q[j];
                    return *this = std::move(r);
                }
                polynomial operator+(const polynomial &q) { polynomial p = *this; p += q; return p; }
                polynomial operator-(const polynomial &q) { polynomial p = *this; p -= q; return p; }
                polynomial operator*(const polynomial &q) { polynomial p = *this; p *= q; return p; }
            };
            template <typename T>
            std::vector<polynomial<T>> add_rank(const std::vector<T>& a) {
                const size_t n = a.size();
                std::vector fs(n, polynomial<T>(bits::count_tz(n) + 1, T{0}));
                for (size_t i = 0; i < n; ++i) fs[i][bits::popcount(i)] = a[i];
                return fs;
            }
            template <typename T>
            std::vector<T> remove_rank(const std::vector<polynomial<T>>& polys) {
                const size_t n = polys.size();
                std::vector<T> a(n);
                for (size_t i = 0; i < n; ++i) a[i] = polys[i][bits::popcount(i)];
                return a;
            }
        }
        template <typename T>
        std::vector<T> subset_convolution(const std::vector<T>& a, const std::vector<T>& b) {
            const size_t n = a.size();
            auto ra = details::add_rank(a);
            auto rb = details::add_rank(b);
            subset_transform::zeta(ra);
            subset_transform::zeta(rb);
            for (size_t i = 0; i < n; ++i) ra[i] *= rb[i];
            subset_transform::mobius(ra);
            return details::remove_rank(ra);
        }
        template <typename T>
        std::vector<T> subset_exp(const std::vector<T>& f) {
            assert(f[0] == 0);
            const size_t n = bits::bit_width(f.size()) - 1;
            std::vector<T> g{1};
            for (size_t i = 0; i < n; ++i) {
                std::vector<T> p(f.begin() + (1 << i), f.begin() + (1 << (i + 1)));
                std::vector<T> h = subset_convolution(std::move(p), g);
                std::move(h.begin(), h.end(), std::back_inserter(g));
            }
            return g;
        }
    }
}

using vertex = size_t;
using vertex_set = size_t;
using edge = std::pair<vertex, vertex>;

std::vector<uint64_t> count_cycles(const size_t n, const size_t, const std::vector<edge> &edges) {
    std::vector adj(n, std::vector<vertex>{});
    for (const auto &[u, v] : edges) adj[u].push_back(v), adj[v].push_back(u);

    std::vector cycle_dp(1u << n, std::vector<uint64_t>(n));
    for (size_t v = 0; v < n; ++v) {
        cycle_dp[1u << v][v] = 1;
    }
    std::vector<uint64_t> cycle(1u << n);
    for (vertex_set s = 1; s < 1u << n; ++s) {
        const vertex start = library::bits::count_tz(s);
        for (vertex cur = 0; cur < n; ++cur) if (cycle_dp[s][cur]) {
            for (const vertex nxt : adj[cur]) {
                if (start == nxt) {
                    cycle[s] += cycle_dp[s][cur];
                } else if (start < nxt and not ((s >> nxt) & 1)) {
                    const vertex_set nxt_s = s | (1u << nxt);
                    cycle_dp[nxt_s][nxt] += cycle_dp[s][cur];
                }
            }
        }
    }
    for (vertex_set s = 1; s < 1u << n; ++s) {
        const size_t popcnt = library::bits::popcount(s);
        if (popcnt == 1) cycle[s] = 1;
        else if (popcnt == 2) cycle[s] = 0;
        else cycle[s] /= 2;
    }
    return cycle;
}

uint64_t solve(const size_t n, const size_t m, const std::vector<edge> &edges) {
    // e[S] := # edges connecting vertices in S.
    std::vector<uint64_t> e(1u << n);
    for (const auto &[u, v] : edges) {
        ++e[(1u << u) | (1u << v)];
    }
    library::subset_transform::zeta(e);

    using sps = std::vector<uint64_t>;

    const sps cycle = count_cycles(n, m, edges);

    sps f(1u << n);
    for (vertex_set C = 1; C < 1u << n; ++C) {
        // max C
        const vertex t = library::bits::bit_width(C) - 1;
        // { 0, ..., t } - C
        const vertex_set S = ((1u << (t + 1)) - 1) ^ C;
        const size_t k = library::bits::popcount(S);
        sps g(1u << k);
        for (vertex_set A = 0; A < 1u << k; ++A) {
            const vertex_set T = library::bits::bit_deposite(A, S, t);
            g[A] = f[T] * (e[T | C] - e[T] - e[C]);
        }
        const sps h = library::set_power_series::subset_exp(g);
        for (vertex_set A = 0; A < 1u << k; ++A) {
            const vertex_set X = library::bits::bit_deposite(A, S, t) | C;
            f[X] += cycle[C] * h[A];
        }
    }
    return library::set_power_series::subset_exp(f).back();
}

int main() {
    size_t n, m;
    std::cin >> n >> m;
    std::vector<edge> edges(m);
    for (auto &[u, v] : edges) {
        std::cin >> u >> v;
        --u, --v;
    }
    std::cout << solve(n, m, edges) << '\n';
}
0