Bell number (Table)
(Mylib/Combinatorics/bell_number_table.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_table(int n) -> [[T]]
  • $B(0,0)$ ~ $B(N,N)$を列挙する
  • Time complexity $O(n^2)$

Requirements

Notes

Problems

References

Verified with

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

Code

#pragma once
#include <vector>

namespace haar_lib {
  template <typename T>
  auto bell_number_table(int n) -> std::vector<std::vector<T>> {
    std::vector<std::vector<T>> ret(n + 1, std::vector<T>(n + 1));

    ret[0][0] = 1;

    for (int i = 1; i <= n; ++i) ret[i][1] = ret[i][i] = 1;

    for (int i = 3; i <= n; ++i) {
      for (int j = 2; j < i; ++j) {
        ret[i][j] = ret[i - 1][j - 1] + j * ret[i - 1][j];
      }
    }

    for (int i = 0; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        ret[i][j] += ret[i][j - 1];
      }
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Combinatorics/bell_number_table.cpp"
#include <vector>

namespace haar_lib {
  template <typename T>
  auto bell_number_table(int n) -> std::vector<std::vector<T>> {
    std::vector<std::vector<T>> ret(n + 1, std::vector<T>(n + 1));

    ret[0][0] = 1;

    for (int i = 1; i <= n; ++i) ret[i][1] = ret[i][i] = 1;

    for (int i = 3; i <= n; ++i) {
      for (int j = 2; j < i; ++j) {
        ret[i][j] = ret[i - 1][j - 1] + j * ret[i - 1][j];
      }
    }

    for (int i = 0; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        ret[i][j] += ret[i][j - 1];
      }
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page