自然数を順序を考慮して分割
問題
ABC132 D - Blue and Red Balls
問題概要
ボール:N個
うち青:K個
ボールを並べて
青の島(青の連続区間の個数)がi個になる並べ方の個数
※同色ボールは区別できない
解法
(Kをi個の自然数に分割する方法 )×(N−Kをi+1個の自然数(両端は0可)に分割する方法)
nをr個の自然数に分割する方法
0を許可するとき,n+r−1Cr−1
これは丸と線で区切る考え方のやつ.
O|OO|O|OO||O|OO|
をシャッフルする,みたいな
0を許可しないために事前に1つ入れておく.
0が許されない箇所がk個あったとき,
n−k+r−1Cr−1