♥沙耶花の備忘録♥

キーエンスプログラミングコンテスト 2019 F Paper Cutting

横の線を $a$ 回, 縦の線を $b$ 回切った時のスコアの総和への寄与は $(a+1)(b+1) {}_H C_{a} {}_W C_b \times (a+bに依存した定数)$ と表せまふ.

$k=1,2,...,K$ に対し, $k=a+b$ となるような $a,b$ に対する $(a+1)(b+1) {}_H C_{a} {}_W C_b$ の総和をまとめて各 $O(1)$ で求められればこの問題が解けまふ.

上記値は, 次の通り数に一致しまふ.

$H$ 個の赤い箱と $W$ 個の青い箱のうち $k$ 個の箱を選び, それぞれに白いボールまたは黒いボールを入れる通り数. ただし, 赤い箱・青い箱に入れられる黒いボールは高々1個.

ここで, 箱同士は区別し, 同じ色のボールは区別しないものとしまふ.

赤い箱・青い箱に入る黒いボールの個数によって場合分けをしまふ. 例えば, ともに1個ずつ入る場合は通り数が次のように求まりまふ.

赤い箱と青い箱から1個ずつ黒いボールを入れる箱を選ぶ通り数( $H \times W$ 通り)に, 残りの箱から $k-2$ 個の箱を選ぶ通り数 ${}_{H+W-2} C_{k-2}$ を掛ける

赤い箱のみに1個入ってる場合・青い箱のみに1個入ってる場合・黒いボールが無い場合も同じ要領で求められるので, これで元の問題が解けまふ.