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

提出ソース

結果

問題	No.2507 Yet Another Subgraph Counting
ユーザー	suisen
提出日時	2023-08-21 22:18:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	8,337 bytes
コンパイル時間	1,196 ms
コンパイル使用メモリ	89,296 KB
実行使用メモリ	11,556 KB
最終ジャッジ日時	2024-05-09 04:31:06
合計ジャッジ時間	11,297 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 11,296 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	111 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	3 ms 6,940 KB
testcase_08	AC	3 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	3 ms 6,940 KB
testcase_11	AC	110 ms 6,940 KB
testcase_12	AC	3 ms 6,940 KB
testcase_13	AC	3 ms 6,940 KB
testcase_14	AC	111 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	110 ms 6,944 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	28 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	3 ms 6,940 KB
testcase_23	AC	111 ms 6,940 KB
testcase_24	AC	8 ms 6,940 KB
testcase_25	AC	477 ms 6,944 KB
testcase_26	TLE	-
testcase_27	AC	111 ms 6,940 KB
testcase_28	AC	475 ms 6,944 KB
testcase_29	AC	4 ms 6,944 KB
testcase_30	TLE	-
testcase_31	TLE	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
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 <cassert>
#include <iostream>
#include <utility>
#include <vector>

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

namespace lib {
    namespace kronecker_power_transform {
        namespace details {
            template <typename UnitTransform, typename ReferenceGetter, std::size_t... Seq>
            void unit_transform(UnitTransform transform, ReferenceGetter ref_getter, std::index_sequence<Seq...>) {
                transform(ref_getter(Seq)...);
            }
        }
        template <typename T, std::size_t D, auto unit_transform>
        void kronecker_power_transform(std::vector<T> &x) {
            const std::size_t n = x.size();
            for (std::size_t block = 1; block < n; block *= D) {
                for (std::size_t l = 0; l < n; l += D * block) {
                    for (std::size_t offset = l; offset < l + block; ++offset) {
                        const auto ref_getter = [&](std::size_t i) -> T& { return x[offset + i * block]; };
                        details::unit_transform(unit_transform, ref_getter, std::make_index_sequence<D>());
                    }
                }
            }
        }
    }

    namespace subset_transform {
        namespace details {
            template <typename T>
            void zeta_unit_transform(T &x0, T &x1) {
                x1 += x0;
            }
            template <typename T>
            void mobius_unit_transform(T &x0, T &x1) {
                x1 -= x0;
            }
        } // namespace details
        template <typename T>
        void zeta(std::vector<T> &a) {
            kronecker_power_transform::kronecker_power_transform<T, 2, details::zeta_unit_transform<T>>(a);
        }
        template <typename T>
        void mobius(std::vector<T> &a) {
            kronecker_power_transform::kronecker_power_transform<T, 2, details::mobius_unit_transform<T>>(a);
        }
    } // namespace subset_transform

    namespace set_power_series {
        namespace details {
            template <typename T>
            struct polynomial : std::vector<T> {
                using std::vector<T>::vector;
            };
        
            template <typename T>
            polynomial<T>& operator+=(polynomial<T>& p, const polynomial<T> &q) {
                assert(p.size() == q.size());
                for (size_t i = 0; i < p.size(); ++i) p[i] += q[i];
                return p;
            }
            template <typename T>
            polynomial<T>& operator-=(polynomial<T>& p, const polynomial<T> &q) {
                assert(p.size() == q.size());
                for (size_t i = 0; i < p.size(); ++i) p[i] -= q[i];
                return p;
            }
            template <typename T>
            polynomial<T>& operator*=(polynomial<T>& p, const polynomial<T> &q) {
                const size_t n = p.size();
                assert(n == q.size());
                polynomial<T> r(n);
                for (size_t i = 0; i < n; ++i) for (size_t j = 0; i + j < n; ++j) r[i + j] += p[i] * q[j];
                p = std::move(r);
                return p;
            }
            template <typename T>
            polynomial<T> operator+(polynomial<T> p, const polynomial<T> &q) { p += q; return p; }
            template <typename T>
            polynomial<T> operator-(polynomial<T> p, const polynomial<T> &q) { p -= q; return p; }
            template <typename T>
            polynomial<T> operator*(polynomial<T> p, const polynomial<T> &q) { p *= q; return p; }

            template <typename T>
            std::vector<polynomial<T>> ranked(const std::vector<T>& a) {
                const int n = a.size();
                std::vector fs(n, polynomial<T>(__builtin_ctz(n) + 1, T{ 0 }));
                for (int i = 0; i < n; ++i) fs[i][__builtin_popcount(i)] = a[i];
                return fs;
            }
            template <typename T>
            std::vector<T> deranked(const std::vector<polynomial<T>>& polys) {
                const int n = polys.size();
                std::vector<T> a(n);
                for (int i = 0; i < n; ++i) a[i] = polys[i][__builtin_popcount(i)];
                return a;
            }
            template <typename T>
            std::vector<polynomial<T>> ranked_zeta(const std::vector<T>& a) {
                std::vector<polynomial<T>> ra = ranked<T>(a);
                subset_transform::zeta(ra);
                return ra;
            }
            template <typename T>
            std::vector<T> deranked_mobius(std::vector<polynomial<T>>& ra) {
                subset_transform::mobius(ra);
                return deranked<T>(ra);
            }
        }

        template <typename T>
        std::vector<T> subset_convolution(const std::vector<T>& a, const std::vector<T>& b) {
            const int n = a.size();
            auto ra = details::ranked_zeta(a), rb = details::ranked_zeta(b);
            for (int i = 0; i < n; ++i) ra[i] *= rb[i];
            return details::deranked_mobius(ra);
        }
        template <typename T>
        std::vector<T> subset_exp(const std::vector<T>& f) {
            assert(f[0] == 0);
            const int n = __builtin_ctz(f.size());
            std::vector<T> g{1};
            for (int 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;
        }
    }

    template <typename T>
    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;
    }
}

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 = __builtin_ctz(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 = __builtin_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)];
    }
    lib::subset_transform::zeta(e);

    using sps = std::vector<uint64_t>;

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

    sps f{0};
    for (vertex v = 0; v < n; ++v) {
        f.resize(1u << (v + 1));
        for (vertex_set x = 1u << v; x < 1u << (v + 1); ++x) {
            const vertex_set full = ((1u << (v + 1)) - 1) ^ x;
            sps g(1u << v);
            for (vertex_set s = full;; --s &= full) {
                g[s] = f[s] * (e[s | x] - e[s] - e[x]);
                if (s == 0) break;
            }
            const sps exp_g = lib::set_power_series::subset_exp(g);
            for (vertex_set s = full;; --s &= full) {
                f[s | x] += cycle[x] * exp_g[s];
                if (s == 0) break;
            }
        }
    }
    return lib::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

結果

テストケース

ソースコード