No.137

No.42 と似ているが, 本問では $A_{k+1}$ が $A_k$ の倍数とは限らない.

そこで, $A_k$ 円硬貨を $i$ 枚使うのを, $A_k, 2A_k, 2^2A_k, \dots 2^jA_k, \dots$ 円硬貨をそれぞれ最大 $1$ 枚使うと考える.

まず最初に $A_1, A_2, \dots, A_N$ 円硬貨を最大 $1$ 枚使って $n$ 円を作る組み合わせの数 $C(n)$ を DP で求める.

残り使える硬貨は $2A_1, 2A_2, \dots, 2A_N, 2^2A_1, 2^2A_2, \dots, 2^2A_N, \dots$ 円硬貨であるので, $M-n$ が偶数にならない DP の結果は捨てていい.

たとえば, $M$ が偶数の場合は, $C(1), C(3), \dots$ は捨てて, $C(0), C(2), \dots$ だけを残す. これを新たな $C(0), C(1), \dots$ にして, $M/2$ を新たな $M$ にして, 残り使える硬貨を $A_1, A_2, \dots, A_N, 2A_1, 2A_2, \dots, 2A_N, \dots$ として DP を続ける.