No.41

$M$ を $111111$ で割った余りは必ず1円で払わなくてはいけない.

$M$ を $111111$ で割った数 (小数点以下切り捨て) を $N$ とすると, $N$ 円を1円玉A, 1円玉B, 2円玉, 3円玉, $\dots$, 9円玉で支払う方法の組み合わせを求める問題となる.

$n$ 円を $k$ 円玉以下で支払う方法の組み合わせを $C(n,k)$ とすると,

$$C(n,k) = C(n,k-1) + C(n-k,k)$$

となり, これを DP で計算して $C(N,9)$ を見る.