AGC002 - F. Leftmost Ball
解法
$ K = 1は明らかなので$ K \geq 2とする。
各色について、最終的な並びにおける先頭位置を$ F_i \, (1 \leq i \leq N)とおくと、$ F_i が昇順になるような配置を数え上げたのち$ N!倍すればよい。
各色について、対応する$ 0が$ F_iより左に存在する。
左側から$ i番目の$ 0が色$ iに対応すると仮定してよい。
同じ数字でも区別し、順序制約をつけることで重複を防ぐことにする。
すると、以下のグラフのトポロジカル順序を数え上げるという問題になる。
$ 0_1 \rightarrow 1_1 \rightarrow \dots \rightarrow 1_{K - 1}
$ \downarrow \qquad \downarrow
$ 0_2 \rightarrow 2_1 \rightarrow \dots \rightarrow 2_{K - 1}
$ \downarrow \qquad \downarrow
$ \vdots \qquad \vdots
$ \downarrow \qquad \downarrow
$ 0_N \rightarrow N_1 \rightarrow \dots \rightarrow N_{K - 1}
左側の$ N \times 2の長方形の部分のみの順序着目する。
右下から順番に置いていくことにする。$ \mathrm{dp}_{i, j}を、一列目は$ i個、二列目は$ j個置いた時点での順序の総数とする。$ i \leq jでなければならない。
遷移は次のようにする。
$ \mathrm{dp}_{i, j}から$ \mathrm{dp}_{i, j + 1}への遷移
この際、$ (N-j)_1, \dots, (N-j)_{K - 1}を一気に配置する。
$ \binom{(j + 1)(K - 2) + i + j}{K - 2}をかける。
$ i < jの時に限り、$ \mathrm{dp}_{i + 1, j}から$ \mathrm{dp}_{i, j}を足す。
これでこの問題を$ O(N(N + K))で解くことができた。