No.189

$M$ ヶ月の中に月の数字和が $k$ になる月が $m(k)$ 月あるとし, $D$ ヶ月の中に日の数字和が $k$ になる日が $d(k)$ 日あるとすると, SUPER HAPPY DAY の合計は

$$\sum_k m(k)d(k)$$

となる.

$n$ 以下の数の中に数字和が $k$ となる数の個数を $C(n, k)$ とおく.

このとき, $C(10^i - 1, k)$ は一番上の桁に着目すると,

$$C(10^i - 1, k) = \sum_{j = 0}^9 C(10^{i - 1} - 1, k - j)$$

となる.

ある数 $p$ の0でない一番下の桁が $i$ 桁目で, その数字が $q$ であり, この桁を0にした数を $r$ としたとき, (たとえば, $p = 25800, r = 25000$ のようなとき)

$$C(p, k) = C(r, k) + \sum_{j = 0}^q C(10^{i} - 1, k - j - S(r))$$

となる. ただし, $S(r)$ は $r$ の数字和である.

あとは $m(k) = C(M, k), d(k) = C(D, k)$ を計算すればいい.

$M, D \leq 10^{200}$ であるので, $k$ は高々 1,800 である.