分割数

問題

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

解法

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

$dp[i][j] = i$ 番目までの品物をちょうど $j$ 個に分割する分割数とします。

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

したがって、 $dp[i][j] = dp[i][j - 1] + dp[i - 1][j]$ となります。こうして $O(nm)$ でこの問題が解けました。

重複組合せ

$(1 \le n \le 1000)$ 種類の品物があり、 $i$ 番目の品物は $1 \le a_i \le 1000$ 個あります。異なる種類の品物は区別できますが、同じ種類の品物は区別できません。これらの品物の中から $1 \le m \le 1000$ 個選ぶ組み合わせの総数を $1 \le mod \le 10000$ で割った値を答えなさい。

解法

$dp[i][j] = i$ 種類目までから $j$ 個選ぶ組み合わせというDPを考えます。この数え上げを、 $i$ 種類目のものを選ぶ場合とそうでない場合に分けて考えます。 $i$ 種類目のものを選ばない場合は $dp[i - 1][j]$ 通りですね。 $i$ 種類目のものを1つ以上選ぶ場合、 $dp[i - 1][j - 1] + dp[i - 1][j - 2] + \ldots + dp[i - 1][max(0, j - a[i])]$ 通りです。これは累積和を同時に求めながら計算すると $O(nm)$ で計算できます（蟻本にはp.67にはこれを上手く変形して累積和なしで計算する方法も載ってあります）。