Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

:warning: Bell(ベル数)
(math/fps/bell.hpp)

概要

ベル数を求める。$n$ 番目(0-indexed) のベル数 $B_n$ は区別できる $n$ 個のボールを任意個のグループに分割する方法の数を与える。

ベル数の母関数 $B(x)$ は以下によって計算される。

$\displaystyle B(x) = \sum_{n=0}^{\infty} B_n \frac {x^n} {n!} = e^{e^x-1}$

使い方

計算量

Code

/**
 * @brief Bell(ベル数)
 * @docs docs/bell.md
 */
template< template< typename > class FPS, typename Mint >
FPS< Mint > bell(int N) {
  FPS< Mint > poly(N + 1), ret(N + 1);
  poly[1] = 1;
  poly = poly.exp();
  poly[0] -= 1;
  poly = poly.exp();
  Mint mul = 1;
  for(int i = 0; i <= N; i++) {
    ret[i] = poly[i] * mul;
    mul *= i + 1;
  }
  return ret;
}
#line 1 "math/fps/bell.hpp"
/**
 * @brief Bell(ベル数)
 * @docs docs/bell.md
 */
template< template< typename > class FPS, typename Mint >
FPS< Mint > bell(int N) {
  FPS< Mint > poly(N + 1), ret(N + 1);
  poly[1] = 1;
  poly = poly.exp();
  poly[0] -= 1;
  poly = poly.exp();
  Mint mul = 1;
  for(int i = 0; i <= N; i++) {
    ret[i] = poly[i] * mul;
    mul *= i + 1;
  }
  return ret;
}
Back to top page