yukicoder No.1011 Infinite Stairs 解説

形式的べき級数による解法

求める値は形式的べき級数から

$ \lbrack x^{K-N}\rbrack (1-x^d)^N/(1-x)^N

$ = \lbrack x^{K-N}\rbrack \sum\binom{N}{i}(-x^d)^i \sum x^j \binom{N+j-1}{j}

$ = \sum_{i=0}^N(-1)^i \binom{N}{i}\binom{N+(K-N-di)-1}{(K-N-di)}

と表せる。計算量は$ O(K)である。

組み合わせ論による解法

これは、K-N個のボールをN個の箱に分ける方法であって、それぞれの箱の中のボールの数がd個未満である場合の数を求めている。N個の箱のうち、少なくともi個の箱がそれぞれd個以上ボールを割り当てられているとする。これはそれらi個の箱にあらかじめd個ボールを割り当てておいて、残りのK-N-di個のボールを自由に分配すると捉えてもよい。i個の箱の選び方がC(N,i)通りだから、そのような場合の数はC(N,i)C(N-1+(K-N-di),K-N-di)通りである。d個以上ボールを割り当てられる箱の数iについて包除原理をすることで求める値は$ \sum_{i=0}^N(-1)^i \binom{N}{i}\binom{N+(K-N-di)-1}{(K-N-di)} 通りとなる。