問題
ポイント
前提として、ある数Xが9の倍数である時、Xを10 進法で表したときの各桁の数字の和も9の倍数となります。すなわち、与えられたKが9の倍数でない場合、条件を満たすXの数は0通りとなります。
Kが9の倍数の場合、動的計画法を使って各桁の値の合計が0~KになるXの数を順番に調べていき、最後に各桁の値の合計がKになるXの数を出力します。
一例として各桁の値の合計が11となるXの数を調べる場合を考えてみます。
Xの右端の数字(1の桁)に注目すると、そこに入る数字は1~9の9通りあります。
1の桁に各数字を入れた場合に、合計が11となる場合の数は
1の桁よりも左の桁の合計が 11- (1の桁に入れた数字) になる場合の数
と同じです。
具体的な数字で見ると
これらの値を動的計画法で求めていきます。
以上を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
K = int(input())
# Kが9の倍数でない場合は0通り
if K % 9 != 0:
print(0)
exit()
dp = [0] * (K+1)
dp[0] = 1 # 最初に設定。各桁の合計が0になる数は1通り
for s in range(1, K+1):
for d in range(1, 10):
if s - d >= 0:
dp[s] += dp[s-d]
dp[s] %= MOD
print(dp[K])
if __name__ == '__main__':
main()
