ふわわあのへや競プロとか、好きなこと、いろいろ。

自然数を順序を考慮して分割

問題

ABC132 D - Blue and Red Balls

問題概要

ボール:NN
うち青:KK
ボールを並べて
青の島(青の連続区間の個数)がii個になる並べ方の個数
※同色ボールは区別できない

解法

(Ki個の自然数に分割する方法 )×(NKi+1個の自然数(両端は0可)に分割する方法)\left( K\text{を}i\text{個の自然数に分割する方法 } \right) \times \left( N-K\text{を}i+1\text{個の自然数(両端は}0\text{可)に分割する方法} \right)

nnrr個の自然数に分割する方法

0\displaystyle 0を許可するとき,n+r1Cr1{}_{n+r-1}C_{r-1}
これは丸と線で区切る考え方のやつ.
O|OO|O|OO||O|OO|をシャッフルする,みたいな

00を許可しないために事前に1つ入れておく.
00が許されない箇所がkk個あったとき,
nk+r1Cr1\displaystyle {}_{n-k+r-1}C_{r-1}