きろく

特筆すべき記録のまとめ

Educational DP Contest:M - Candies

問題

atcoder.jp

解法

dp(i, j) := i 人目までで j 個分けるときの通り数

と定義する.このとき,

dp(i, j) = dp(i - 1, j) + dp(i - 1, j - 1) + ... + dp(i - 1, j - a_(i - 1))

dp(i, j) = 1 (j == 0 のとき)

dp(i, j) = 0 (j < 0, i == 0 のとき)

と漸化式が立つが,これでは遷移が O(a_i) となってしまい TLE になってしまうので,漸化式の置き方を工夫することで,

dp(i, j) = dp(i - 1, j) + dp(i, j - 1) - dp(i - 1, j - a_(i - 1) - 1)

と遷移が O(1) に抑えることが出来る.O(NK).

解答

atcoder.jp

mod を取る系の数え上げはこうした漸化式を工夫して変形させるテクが使えるらしい.

f:id:babcs2035:20190107172741p:plain