意味
- N人をKグループに分割する方法
- N>=K
- グループは区別しない(箱に名前はない)し、箱の順番もない ( (1,3,1)と(1,1,3)などは同じものとする)
AC
- (old, 漸化式埋めVER) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3786812#1
- (new, memo) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4876088#1
計算量
- O(NK)
読んだ(すごい)
- drkenさんの12相まとめ
- https://qiita.com/drken/items/f2ea4b58b0d21621bd51
検索用タグ
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; }
ついでにベル数も
- ベル数はstirling numberから求まる
- AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4876155#1