蟻本リーディング 組み合わせ編

飛行機の移動が暇なので蟻本を読んでまとめることにしました。

今回は組み合わせ問題編です。

分割数

問題

個の互いに区別できない品物を個以下に分割する方法の場合の数をで割ったあまりを求めよ。 たとえば、4つの品物を(1, 1, 2)と分割するのと(1, 2, 1)と分割するのは同じ分割だと数えます。

解法

mod素数の場合、combinationがで求められることにより、事前計算も込みでで解くことができます。 modが素数でない場合は、コンビネーション計算時に逆元が求まらないので、DPをします。

番目までの品物をちょうど個に分割する分割数とします。

ちょうど個に分割する方法は、番目までの品物が個に分割されていて番目の品物を別の1グループとする場合と、 番目までの品物がグループに分割されていて、i番目の品物をどれかに追加する、という場合になります。

したがって、となります。 こうしてでこの問題が解けました。

重複組合せ

種類の品物があり、番目の品物は個あります。異なる種類の品物は区別できますが、同じ種類の品物は区別できません。これらの品物の中から個選ぶ組み合わせの総数をで割った値を答えなさい。

解法

種類目までから個選ぶ組み合わせというDPを考えます。この数え上げを、種類目のものを選ぶ場合とそうでない場合に分けて考えます。 種類目のものを選ばない場合は通りですね。種類目のものを1つ以上選ぶ場合、通りです。これは累積和を同時に求めながら計算するとで計算できます（蟻本にはp.67にはこれを上手く変形して累積和なしで計算する方法も載ってあります）。