Submission #35619076

Source Code Expand

mod = 1000000007

k = int(input())

# x mod 9 = (xの各桁の数の和) mod 9

if k % 9 != 0:
    print(0)
else:
    # 各桁の数の和がKである、かつ、各桁が0でない、整数の数を計算する

    # 先頭の桁が1のとき、[各桁の和がKの整数] = 1[各桁の和がK-1の整数]
    # 先頭の桁が2のとき、[各桁の和がKの整数] = 2[各桁の和がK-2の整数]
    # ...
    # 先頭の桁が9のとき、[各桁の和がKの整数] = 9[各桁の和がK-9の整数]

    # dp[K]=(Xの数 mod 9)なDPを考える

    dp = [0]*(k+1)
    dp[0] = 1
    for i in range(1, k+1):
        max_j = min(i, 9)
        for j in range(1, max_j+1):
            dp[i] += dp[i-j]

    print(dp[k]%mod)

Submission Info

Submission Time
Task 042 - Multiple of 9（★4）
User inaty
Language Python (3.8.2)
Score 4
Code Size 754 Byte
Status AC
Exec Time 1957 ms
Memory 664004 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 4 / 4
Status
AC × 2
AC × 62
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 11_large_00.txt, 11_large_01.txt, 11_large_02.txt, 11_large_03.txt, 11_large_04.txt, 11_large_05.txt, 11_large_06.txt, 11_large_07.txt, 11_large_08.txt, 11_large_09.txt, 11_large_10.txt, 11_large_11.txt, 11_large_12.txt, 11_large_13.txt, 11_large_14.txt, 11_large_15.txt, 11_large_16.txt, 11_large_17.txt, 11_large_18.txt, 11_large_19.txt, 99_hand_00.txt, 99_hand_01.txt, 99_hand_02.txt, 99_hand_03.txt, 99_hand_04.txt, 99_hand_05.txt, 99_hand_06.txt, 99_hand_07.txt, 99_hand_08.txt, 99_hand_09.txt, 99_hand_10.txt, 99_hand_11.txt, 99_hand_12.txt, 99_hand_13.txt, 99_hand_14.txt, 99_hand_15.txt, 99_hand_16.txt, 99_hand_17.txt, 99_hand_18.txt, 99_hand_19.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 25 ms 8816 KiB
00_sample_01.txt AC 17 ms 8808 KiB
10_small_00.txt AC 18 ms 8896 KiB
10_small_01.txt AC 22 ms 8888 KiB
10_small_02.txt AC 17 ms 8816 KiB
10_small_03.txt AC 17 ms 8832 KiB
10_small_04.txt AC 17 ms 8828 KiB
10_small_05.txt AC 17 ms 8992 KiB
10_small_06.txt AC 17 ms 8900 KiB
10_small_07.txt AC 17 ms 8924 KiB
10_small_08.txt AC 21 ms 8812 KiB
10_small_09.txt AC 17 ms 9076 KiB
10_small_10.txt AC 18 ms 8904 KiB
10_small_11.txt AC 19 ms 8828 KiB
10_small_12.txt AC 17 ms 8928 KiB
10_small_13.txt AC 17 ms 8964 KiB
10_small_14.txt AC 18 ms 8900 KiB
10_small_15.txt AC 17 ms 8972 KiB
10_small_16.txt AC 18 ms 8812 KiB
10_small_17.txt AC 18 ms 8932 KiB
10_small_18.txt AC 19 ms 8816 KiB
10_small_19.txt AC 17 ms 8992 KiB
11_large_00.txt AC 1747 ms 538268 KiB
11_large_01.txt AC 1619 ms 539888 KiB
11_large_02.txt AC 1600 ms 540052 KiB
11_large_03.txt AC 1608 ms 540264 KiB
11_large_04.txt AC 1614 ms 540464 KiB
11_large_05.txt AC 1615 ms 540540 KiB
11_large_06.txt AC 1607 ms 540640 KiB
11_large_07.txt AC 1610 ms 540580 KiB
11_large_08.txt AC 1614 ms 540696 KiB
11_large_09.txt AC 1605 ms 540984 KiB
11_large_10.txt AC 1613 ms 540904 KiB
11_large_11.txt AC 1608 ms 541004 KiB
11_large_12.txt AC 1610 ms 541260 KiB
11_large_13.txt AC 1625 ms 541216 KiB
11_large_14.txt AC 1607 ms 541316 KiB
11_large_15.txt AC 1624 ms 541532 KiB
11_large_16.txt AC 1612 ms 541708 KiB
11_large_17.txt AC 1620 ms 541792 KiB
11_large_18.txt AC 1613 ms 541816 KiB
11_large_19.txt AC 1608 ms 541852 KiB
99_hand_00.txt AC 22 ms 8872 KiB
99_hand_01.txt AC 19 ms 8900 KiB
99_hand_02.txt AC 58 ms 15740 KiB
99_hand_03.txt AC 1957 ms 664004 KiB
99_hand_04.txt AC 17 ms 8888 KiB
99_hand_05.txt AC 17 ms 8884 KiB
99_hand_06.txt AC 22 ms 8824 KiB
99_hand_07.txt AC 17 ms 8896 KiB
99_hand_08.txt AC 25 ms 8680 KiB
99_hand_09.txt AC 17 ms 8676 KiB
99_hand_10.txt AC 16 ms 8884 KiB
99_hand_11.txt AC 18 ms 8676 KiB
99_hand_12.txt AC 18 ms 8824 KiB
99_hand_13.txt AC 21 ms 8672 KiB
99_hand_14.txt AC 21 ms 8828 KiB
99_hand_15.txt AC 17 ms 8780 KiB
99_hand_16.txt AC 18 ms 8840 KiB
99_hand_17.txt AC 20 ms 8888 KiB
99_hand_18.txt AC 17 ms 8680 KiB
99_hand_19.txt AC 17 ms 8888 KiB