graph/count/count_labeled_undirected.hpp

• View this file on GitHub
• Last update: 2024-01-29 21:47:23+09:00
• Include: #include "graph/count/count_labeled_undirected.hpp"
• Link: https://oeis.org/A006125

Required by

• graph/count/count_labeled_biconnected.hpp
• graph/count/count_labeled_bridgeless.hpp
• graph/count/count_labeled_connected.hpp
• graph/count/count_labeled_eulerian.hpp

Verified with

• test/mytest/count_labeled_biconnected.test.cpp
• test/mytest/count_labeled_bridgeless.test.cpp
• test/mytest/count_labeled_connected.test.cpp
• test/mytest/count_labeled_eulerian.test.cpp
• test/mytest/count_labeled_undirected.test.cpp

Code

// https://oeis.org/A006125
template <typename mint>
vc<mint> count_labeled_undirected(int N) {
  vc<mint> F(N + 1);
  mint pow2 = 1;
  F[0] = 1;
  FOR(i, 1, N + 1) F[i] = F[i - 1] * pow2, pow2 += pow2;
  return F;
}

#line 1 "graph/count/count_labeled_undirected.hpp"
// https://oeis.org/A006125
template <typename mint>
vc<mint> count_labeled_undirected(int N) {
  vc<mint> F(N + 1);
  mint pow2 = 1;
  F[0] = 1;
  FOR(i, 1, N + 1) F[i] = F[i - 1] * pow2, pow2 += pow2;
  return F;
}

Back to top page