Bell number
(Mylib/Combinatorics/bell_number.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• bell_number<ft>(int n, int k) -> T
  • Time complexity $O(\min(k, n)\ \log n)$

Requirements

Notes

Problems

References

• https://mathtrain.jp/zensya
• https://mathtrain.jp/twelveway
• https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E6%95%B0

Depends on

• Factorial table (Mylib/Combinatorics/factorial_table.cpp)

Verified with

• test/aoj/DPL_5_G/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>
#include "Mylib/Combinatorics/factorial_table.cpp"

namespace haar_lib {
  template <
      const auto &ft,
      typename T = typename std::remove_reference_t<decltype(ft)>::value_type>
  T bell_number(int n, int k) {
    if (n == 0) return T(1);

    k = std::min(k, n);

    std::vector<T> t(k, 1);

    for (int i = 1; i < k; ++i) {
      if (i % 2 == 0)
        t[i] = t[i - 1] + ft.inv_factorial(i);
      else
        t[i] = t[i - 1] - ft.inv_factorial(i);
    }

    T ret = 0;
    for (int i = 1; i <= k; ++i) {
      ret += t[k - i] * T::pow(i, n) * ft.inv_factorial(i);
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Combinatorics/bell_number.cpp"
#include <algorithm>
#include <vector>
#line 2 "Mylib/Combinatorics/factorial_table.cpp"
#include <cassert>
#include <cstdint>
#line 5 "Mylib/Combinatorics/factorial_table.cpp"

namespace haar_lib {
  template <typename T>
  class factorial_table {
  public:
    using value_type = T;

  private:
    int N_;
    std::vector<T> f_table_, if_table_;

  public:
    factorial_table() {}
    factorial_table(int N) : N_(N) {
      f_table_.assign(N + 1, 1);
      if_table_.assign(N + 1, 1);

      for (int i = 1; i <= N; ++i) {
        f_table_[i] = f_table_[i - 1] * i;
      }

      if_table_[N] = f_table_[N].inv();

      for (int i = N; --i >= 0;) {
        if_table_[i] = if_table_[i + 1] * (i + 1);
      }
    }

    T factorial(int64_t i) const {
      assert(0 <= i and i <= N_);
      return f_table_[i];
    }

    T inv_factorial(int64_t i) const {
      assert(0 <= i and i <= N_);
      return if_table_[i];
    }

    T P(int64_t n, int64_t k) const {
      if (n < k or n < 0 or k < 0) return 0;
      return factorial(n) * inv_factorial(n - k);
    }

    T C(int64_t n, int64_t k) const {
      if (n < k or n < 0 or k < 0) return 0;
      return P(n, k) * inv_factorial(k);
    }

    T H(int64_t n, int64_t k) const {
      if (n == 0 and k == 0) return 1;
      return C(n + k - 1, k);
    }
  };
}  // namespace haar_lib
#line 5 "Mylib/Combinatorics/bell_number.cpp"

namespace haar_lib {
  template <
      const auto &ft,
      typename T = typename std::remove_reference_t<decltype(ft)>::value_type>
  T bell_number(int n, int k) {
    if (n == 0) return T(1);

    k = std::min(k, n);

    std::vector<T> t(k, 1);

    for (int i = 1; i < k; ++i) {
      if (i % 2 == 0)
        t[i] = t[i - 1] + ft.inv_factorial(i);
      else
        t[i] = t[i - 1] - ft.inv_factorial(i);
    }

    T ret = 0;
    for (int i = 1; i <= k; ++i) {
      ret += t[k - i] * T::pow(i, n) * ft.inv_factorial(i);
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page