結果
問題 | No.2507 Yet Another Subgraph Counting |
ユーザー |
|
提出日時 | 2023-08-21 23:03:01 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 265 ms / 2,000 ms |
コード長 | 9,140 bytes |
コンパイル時間 | 1,397 ms |
コンパイル使用メモリ | 90,720 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 14:15:00 |
合計ジャッジ時間 | 5,876 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 52 |
ソースコード
#include <cassert>#include <iostream>#include <limits>#include <utility>#include <vector>namespace lib {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);}}}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 detailstemplate <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_transformnamespace 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][bits::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][bits::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;}}}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 = __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 = lib::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)];}lib::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 Cconst vertex t = lib::bits::bit_width(C) - 1;// { 0, ..., t } - Cconst vertex_set S = ((1u << (t + 1)) - 1) ^ C;const size_t k = lib::bits::popcount(S);sps g(1u << k);for (vertex_set A = 0; A < 1u << k; ++A) {const vertex_set T = lib::bits::bit_deposite(A, S, t);g[A] = f[T] * (e[T | C] - e[T] - e[C]);}const sps h = lib::set_power_series::subset_exp(g);for (vertex_set A = 0; A < 1u << k; ++A) {const vertex_set X = lib::bits::bit_deposite(A, S, t) | C;f[X] += cycle[C] * h[A];}}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';}