重複組み合わせ

内容

n種類の商品がそれぞれv[i]個ある。
同じ種類の商品は区別しないが、別の種類の商品は区別するとき、これらの商品からM個取り出す組み合わせの数

考え方

dp[i+1][j]:=商品iまで使って個数j個選ぶ組み合わせの数

漸化式は、商品i-1まででj-k個選んで、商品iでk個選ぶと、商品iでj個選ぶ組み合わせが得られる。
dp[i+1][j]:=Σ_{k=0}^{min(j,v[i])} {dp[i][j-k]}
これだと、iとjとkでループができるので、O(nm^2)。

ここで、累積和として考えると、

Xを求めるには、AとBとCの値だけでいいことがわかる。
すると、kのループが必要なくなるので、O(nm)。

実装的には、dp[0][0]は、「商品を一つも使わずに1つも選ばない選び方」になるので、1通りとする。
図のAやCは位置によっては存在しないので、存在しない場合は0通りとして考える。

その他

http://arc028.contest.atcoder.jp/tasks/arc028_4
ある商品kを必ずxだけ使う場合の組み合わせの数は、i==kの時だけxを使う場合のみの1通りになる。
なので、dp[i+1][j] = dp[i][j-x]とそのまま次の商品に渡してあげればよい。