ABC231 G - Balls in Boxes - ツバサの備忘録

解法

$\prod _{i = 1}^{N} B_{i}$ の総和を求めて、最後に全パターン数 $N^{k}$ で割れば答えです。総和の求め方について考えていきます。

$\prod _{i = 1}^{N} B_{i}$ は、 $N$ 個の箱にあるボール $B_{i}$ 個からそれぞれ1個ずつ選ぶパターン数と一致します。
$\prod_{i =1}^{N}\ _{B_{i}}C_{1}$ ということです。

$i$ 個目の箱にあるボール $B_{i}$ からボールを選ぶパターンは2パターンあります。
最初から入っている $A_{i}$ 個のボールを選ぶパターンと、新しく追加された $B_{i} - A_{i}$ 個のボールを選ぶパターンです。
前者は明らかに $A_{i}$ 通りです。

$N$ 個の箱の中で、前者を選ぶグループを決めていきます。すると、前者を選んだ箱 $p$ における $\prod A_{p}$ に、 $K$ 回のボールの入れ方、および後者を選んだ箱のボールの選び方をかけたものを足していけば答えです。
新しく追加するボールの入れ方や選び方は、前者を選んだ数に依存します。なので、 $\prod A_{p}$ をあらかじめまとめて足しておきます。
これは、

$dp[i][j] = i$ 番目の箱までみて、 $j$ 個の箱を前者として選んだ状態における、 $\prod A_{p}$ の総和

として計算していくことができます。

では、 $dp[N][i]$ にかけるべき数を計算していきます。やることは2つで、

$K$ 個のボールのうち、 $N-i$ 個の選ばれるべきボールの位置を決める
残ったボールを箱に振り分ける

です。

1つめについて考えます。まだ選ばれてない箱の番号が $\{a,b,c\}$ だったとします。この時、 $K$ 回の操作のうち3つをとってきて並べた列 $\{x,y,z\}$ を作ると、前から順番に $a,b,c$ に割り当てることで、過不足なく数えることができます。つまり、 $K$ 個の中から $N-i$ 個選んで並べるパターン数になり、 $\ _{K}P_{N-i}$ となります。