No.42

$c_0 = 1,\ c_1 = 5, \dots,\ c_5 = 500$ とする.

$c_k$ 円以下の硬貨で $M$ 円を支払う組み合わせの数を $f(k, M)$ とすると,

$$f(k, M) = f(k-1, M) + f(k-1, M - c_k) + f(k-1, M - 2c_k) + \dots + f(k-1, M - mc_k)$$

となる. $M$ が大きいので上記の DP では間に合わない.

ここで, $M = mc_k + a$ とすると,

$$f(k, mc_k + a) = f(k-1, mc_k + a) + f(k-1, (m-1)c_k + a) + \dots + f(k-1, a)$$

となる.

$f(k, mc_k + a)$ が $m$ の $k$ 次式と仮定すると, $f(k-1, mc_{k-1} + a)$ は $m$ の $k-1$ 次式となる.

このとき, $c_k$ は $c_{k-1}$ の倍数なので, $f(k-1, mc_k + a) = f(k-1, mbc_{k-1} + a)$ となり, $f(k-1, mbc_{k-1} + a)$ も $m$ の $k-1$ 次式となる.

よって, $f(k, mc_k + a)$ は $m$ 個の $k-1$ 次式の和なので, $k$ 次式となる.

$f(0, *) = 1$ であるので, これは $k$ の $0$ 次式であり, 数学的帰納法により仮定は正しいと証明される.

$f(k, mc_k + a)$ は $k$ 次式であるとわかったので, $k+1$ 個の値があればラグランジュ補間で任意の $m$ に対する値を求めることができる.

問題では $k = 5$ なので $6$ 個の値, すなわち $M \leq 3000$ の範囲で DP で $f(5, M)$ を求めておけばいい.