説明

ベル数 $B(n,k)$ を求める。

区別できる $n$ 個のボールを区別できない $k$ 個以下の箱に分割する方法の数を与える。

特に $B(n,n)$ は $n$ 個のボールを任意個のグループに分割する方法の数である。

計算量

  • $O(\min(n, k) \log n)$

実装例

依存ライブラリ Mod-Int Combination

  • bell_number($n$, $k$):= $B(n,k)$ を返す
template< typename T >
T bell_number(int n, int k) {
  if(n == 0) return 1;
  k = min(k, n);
  Combination< T > uku(k);
  T ret = 0;
  vector< T > pref(k + 1);
  pref[0] = 1;
  for(int i = 1; i <= k; i++) {
    if(i & 1) pref[i] = pref[i - 1] - uku.rfact(i);
    else pref[i] = pref[i - 1] + uku.rfact(i);
  }
  for(int i = 1; i <= k; i++) {
    ret += T(i).pow(n) * uku.rfact(i) * pref[k - i];
  }
  return ret;
}

検証

AOJ DPL_5_G ボールと箱 7

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_5_G"

#include "../../template/template.cpp"

#include "../mod-int.cpp"
#include "../combination.cpp"

#include "../bell-number.cpp"

int main() {
  int N, K;
  cin >> N >> K;
  cout << bell_number< modint >(N, K) << endl;
}