スターリング数 stirling number (& ベル数 bell number)

ライブラリ

意味

  • N人をKグループに分割する方法
    • N>=K
    • グループは区別しない（箱に名前はない）し、箱の順番もない ( (1,3,1)と(1,1,3)などは同じものとする)

AC

計算量

  • O(NK)

読んだ（すごい）

検索用タグ

starling (間違い)

code

// スターリング数
// k個へのグループ分け
const int N_MAX = 1050;
ll memo[N_MAX][N_MAX];
bool stirling_memo_initialized=false;
void reset(){
  stirling_memo_initialized=true;
  rep(i,N_MAX){
    rep(j,N_MAX){
      memo[i][j]=-1;
    }
  }
}
ll stirling_number(ll n, ll k){
  if(!stirling_memo_initialized){
    cerr<<"need initialize"; exit(0);
  }
  if(memo[n][k]!=-1)return memo[n][k];
  if(n<k)return 0;
  if(n==0)return 0;
  if(k==0)return 0;
  if(n==k)return 1;
  return memo[n][k] = (stirling_number(n-1,k-1) + k * stirling_number(n-1,k)) % mod;
}

// ベル数
ll bell_number(ll n, ll k){
  mint m = 0;
  rep(i,k+1){
    m += stirling_number(n,i);
  }
  return m.x;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll n,k;cin>>n>>k;

    reset();
    ll ans = stirling_number(n,k);
    p(ans);
    
    return 0;
}

ついでにベル数も