水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

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