典型90 042 – Multiple of 9（★4）｜かえるのほんだな

競プロの精進のために学びがあった問題についてまとめています。目標は AtCoder 水色！

今のレートは茶色です。

問題

典型90 042 – Multiple of 9（★4）を解きました。

考察

各桁の和がちょうどKになり、かつ9の倍数であるような数がいくつ作れるか、という問題。

数の性質として、各桁の和が9の倍数になるとき、その数もまた9の倍数になる。

つまり、与えられたKが9の倍数でない場合は、必然的に答えは0通りになる。

次に、Kが9の倍数である場合については、桁に0を含まないことから、足してKになるすべてのパターンを列挙すれば良い。

例えば、先頭行の値が1~9それぞれの場合、次の桁は、

1 K-1
2 K-2
3 K-3
4 K-4
5 K-5
6 K-6
7 K-7
8 K-8
9 K-9

となる。

これを、dp[各桁の和] = 通り数というDPで求めていく。

すべてのKに対して、各桁の和がKとなる場合の通り数は、各桁の和が”K-1” ~ “K-9”になる場合の通り数の和と等しい。

コード

K = int(input())
mod = int(pow(10,9) + 7)
if K % 9 != 0:
    print(0)
    exit()
 
# dp[各桁の和] = 通り数
dp = [0] * (K + 1)
dp[0] = 1


for i in range(1, K + 1):
    # 9未満の場合は0なので無視して良い
    m = min(9, i)

    # Kまでのすべての値に対して、"K-1" から "K-9" までの通り数の和を求めていく
    for j in range(1, m + 1):
        dp[i] += dp[i - j]

    dp[i] %= mod
print(dp[K])