#909165 (C++17) No.2507 Yet Another Subgraph Counting

提出ソース

結果

問題	No.2507 Yet Another Subgraph Counting
ユーザー	suisen
提出日時	2023-08-31 20:25:51
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	9,857 bytes
コンパイル時間	1,062 ms
コンパイル使用メモリ	93,180 KB
実行使用メモリ	10,752 KB
最終ジャッジ日時	2024-06-11 01:33:30
合計ジャッジ時間	9,230 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 10,752 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 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	1 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	7 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	4 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 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	36 ms 5,376 KB
testcase_24	AC	3 ms 5,376 KB
testcase_25	AC	76 ms 5,376 KB
testcase_26	AC	620 ms 5,376 KB
testcase_27	AC	23 ms 5,376 KB
testcase_28	AC	102 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	645 ms 5,376 KB
testcase_31	AC	12 ms 5,404 KB
testcase_32	AC	12 ms 5,376 KB
testcase_33	AC	4 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB
testcase_37	TLE	-
testcase_38	TLE	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

// TLE O(4^n n^2)

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

constexpr size_t N_MAX = 13;

namespace library {
    namespace bits {
        template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
        T kth_bit(T v, size_t k) { return (v >> k) & 1; }
        template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
        size_t bit_length(const T v) {
            if constexpr (std::numeric_limits<std::make_unsigned_t<T>>::digits <= 32) {
                return 32 - __builtin_clz(v);
            } else {
                return 64 - __builtin_clzll(v);
            }
        }
        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 subset_transform {
        template <typename T> void zeta(std::vector<T>& x) {
            const size_t n = x.size();
            for (size_t b = 1; b < n; b *= 2) for (size_t l = 0; l < n; l += 2 * b) for (size_t i = l; i < l + b; ++i) {
                x[i + 1 * b] += x[i + 0 * b];
            }
        }
        template <typename T> void mobius(std::vector<T>& x) {
            const size_t n = x.size();
            for (size_t b = 1; b < n; b *= 2) for (size_t l = 0; l < n; l += 2 * b) for (size_t i = l; i < l + b; ++i) {
                x[i + 1 * b] -= x[i + 0 * b];
            }
        }
    }

    namespace set_power_series {
        namespace details {
            struct polynomial {
                polynomial() : polynomial(0) {}
                explicit polynomial(size_t n, uint64_t value = {}) { assign(n, value); }

                size_t size() const { return _size; }

                uint64_t& operator[](size_t i) { return _data[i]; }
                const uint64_t& operator[](size_t i) const { return _data[i]; }

                void assign(size_t n, uint64_t v) {
                    _size = std::min(n, N_MAX + 1);
                    std::fill(_data.begin(), _data.begin() + _size, v);
                }
                void resize(size_t n, uint64_t v) {
                    size_t nxt_size = std::min(n, N_MAX + 1);
                    if (nxt_size > _size) {
                        std::fill(_data.begin() + _size, _data.begin() + nxt_size, v);
                        _size = nxt_size;
                    }
                }
                void push_front(uint64_t v) {
                    uint64_t back = _data[_size - 1];
                    for (size_t i = _size; i --> 1;) {
                        _data[i] = _data[i - 1];
                    }
                    _data[0] = v;
                    if (_size != N_MAX + 1) {
                        _data[_size++] = back;
                    }
                }
                
                polynomial& operator+=(const polynomial& q) {
                    const size_t n = 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();
                    for (size_t i = 0; i < q.size(); ++i) (*this)[i] -= q[i];
                    return *this;
                }
                polynomial& operator*=(const polynomial& q) {
                    const size_t n = size(), m = q.size();
                    resize(n + m - 1, 0);
                    const size_t k = size();
                    for (size_t i = n; i --> 0;) {
                        const uint64_t v = std::exchange((*this)[i], 0);
                        const size_t jmax = std::min(k - i, m);
                        for (size_t j = 0; j < jmax; ++j) {
                            (*this)[i + j] += v * q[j];
                        }
                    }
                    return *this;
                }
                polynomial& muleq(const polynomial& q, size_t siz) {
                    const size_t n = size(), m = q.size();
                    resize(std::min(siz, n + m - 1), 0);
                    const size_t k = size();
                    for (size_t i = n; i --> 0;) {
                        const uint64_t v = std::exchange((*this)[i], 0);
                        const size_t jmax = std::min(k - i, m);
                        for (size_t j = 0; j < jmax; ++j) {
                            (*this)[i + j] += v * q[j];
                        }
                    }
                    return *this;
                }
            private:
                std::array<uint64_t, N_MAX + 1> _data;
                size_t _size;
            };

            template <typename InputIterator>
            std::vector<polynomial> add_rank(InputIterator first, InputIterator last) {
                const size_t n = last - first;
                std::vector<polynomial> fs(n);
                for (size_t i = 0; i < n; ++i) {
                    size_t popc = bits::popcount(i);
                    fs[i].assign(popc + 1, 0);
                    fs[i][popc] = first[i];
                }
                return fs;
            }
            std::vector<polynomial> add_rank(const std::vector<uint64_t> &a) {
                return add_rank(a.begin(), a.end());
            }
            std::vector<uint64_t> remove_rank(const std::vector<polynomial>& polys) {
                const size_t n = polys.size();
                std::vector<uint64_t> a(n);
                for (size_t i = 0; i < n; ++i) a[i] = polys[i][bits::popcount(i)];
                return a;
            }
        }
        
        std::vector<uint64_t> subset_exp(const std::vector<uint64_t>& f) {
            assert(f[0] == 0);
            const size_t n = bits::bit_length(f.size()) - 1;
            auto rf = details::add_rank({ 1 });
            rf.reserve(size_t(1) << n);
            for (size_t i = 0; i < n; ++i) {
                auto rg = details::add_rank(f.begin() + (1 << i), f.begin() + (1 << (i + 1)));
                subset_transform::zeta(rg);
                for (size_t j = 0; j < size_t(1) << i; ++j) {
                    rg[j].push_front(1);
                    rg[j].muleq(rf[j], i + 2);
                    rf.push_back(rg[j]);
                }
            }
            subset_transform::mobius(rf);
            return details::remove_rank(rf);
        }
    }
}

using vertex = size_t;
using vertex_set = size_t;
using edge = std::pair<vertex, vertex>;
using Int = uint64_t;
using set_power_series = std::vector<Int>;

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

    // "c" mentioned in the editorial
    std::vector<Int> c(1u << n);

    // dp[S: vertex set][v: vertex] := # simple paths from min S to v passing vertices in S (but not passing vertices not in S)
    std::vector dp(1u << n, std::vector<Int>(n));
    // base cases
    for (vertex v = 0; v < n; ++v) {
        dp[1u << v][v] = 1;
    }

    for (vertex_set S = 1; S < 1u << n; ++S) {
        // min S
        const vertex start = library::bits::count_tz(S);
        for (vertex cur = 0; cur < n; ++cur) for (const vertex nxt : adj[cur]) {
            if (start == nxt) {
                c[S] += dp[S][cur];
            } else if (start < nxt and not library::bits::kth_bit(S, nxt)) {
                const vertex_set T = S | (1u << nxt);
                dp[T][nxt] += dp[S][cur];
            }
        }
    }

    for (vertex_set S = 1; S < 1u << n; ++S) {
        const size_t card = library::bits::popcount(S);
        if (card == 1) c[S] = 1;
        if (card == 2) c[S] = 0;
        if (card >= 3) c[S] /= 2;
    }
    return c;
}

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

    // "c" mentioned in the editorial
    const set_power_series c = count_cycles(n, m, edges);

    // "f" mentioned in the editorial
    set_power_series f(1u << n);
    for (vertex_set C = 1; C < 1u << n; ++C) if (c[C]) {
        // max C
        const vertex t = library::bits::bit_length(C) - 1;
        // {0, ..., t} - C
        const vertex_set S = ((1u << (t + 1)) - 1) ^ C;
        // "g_C" mentioned in the editorial
        set_power_series g(1u << t);
        for (vertex_set T = S;; --T &= S) {
            g[T] = f[T] * (E[T | C] - E[T] - E[C]);
            if (T == 0) break;
        }
        // "h_C" mentioned in the editorial
        const set_power_series h = library::set_power_series::subset_exp(g);
        for (vertex_set T = S;; --T &= S) {
            f[C | T] += c[C] * h[T];
            if (T == 0) break;
        }
    }
    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';
}

yukicoder

結果

テストケース

ソースコード