結果
問題 | No.1407 Kindness |
ユーザー | None |
提出日時 | 2021-02-26 21:49:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 1,912 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 82,080 KB |
最終ジャッジ日時 | 2024-04-10 12:27:46 |
合計ジャッジ時間 | 3,486 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
52,948 KB |
testcase_01 | AC | 36 ms
53,312 KB |
testcase_02 | AC | 34 ms
52,900 KB |
testcase_03 | AC | 36 ms
53,372 KB |
testcase_04 | AC | 36 ms
52,996 KB |
testcase_05 | AC | 35 ms
52,700 KB |
testcase_06 | AC | 36 ms
52,772 KB |
testcase_07 | AC | 36 ms
53,496 KB |
testcase_08 | AC | 36 ms
54,068 KB |
testcase_09 | AC | 36 ms
52,624 KB |
testcase_10 | AC | 36 ms
53,072 KB |
testcase_11 | AC | 36 ms
52,492 KB |
testcase_12 | AC | 77 ms
81,144 KB |
testcase_13 | AC | 52 ms
68,268 KB |
testcase_14 | AC | 54 ms
69,980 KB |
testcase_15 | AC | 77 ms
80,840 KB |
testcase_16 | AC | 67 ms
79,016 KB |
testcase_17 | AC | 56 ms
72,048 KB |
testcase_18 | AC | 58 ms
72,480 KB |
testcase_19 | AC | 73 ms
80,484 KB |
testcase_20 | AC | 70 ms
79,852 KB |
testcase_21 | AC | 47 ms
64,308 KB |
testcase_22 | AC | 48 ms
64,408 KB |
testcase_23 | AC | 70 ms
79,344 KB |
testcase_24 | AC | 83 ms
82,080 KB |
testcase_25 | AC | 58 ms
72,356 KB |
testcase_26 | AC | 60 ms
75,648 KB |
testcase_27 | AC | 48 ms
64,676 KB |
testcase_28 | AC | 76 ms
81,152 KB |
testcase_29 | AC | 47 ms
63,304 KB |
testcase_30 | AC | 79 ms
81,352 KB |
testcase_31 | AC | 52 ms
69,316 KB |
testcase_32 | AC | 72 ms
80,724 KB |
testcase_33 | AC | 53 ms
69,088 KB |
testcase_34 | AC | 67 ms
79,296 KB |
testcase_35 | AC | 51 ms
67,772 KB |
testcase_36 | AC | 45 ms
62,672 KB |
testcase_37 | AC | 77 ms
81,952 KB |
ソースコード
def digit(N): """ :param N: 0 <= n <= N の整数 (※ 下限が 1 の場合は返り値を -= 1 等する) :param M: 状態数 E[i][*]: 上からi桁目までが N と一致 (した時の状態数) S[i][*]: 上からi桁目までで N より小さい事が確定 (した時の状態数) """ L = len(N) E,S = [[0 for _ in range(L+1)] for _ in range(2)] E[0] = 1 S[0] = 0 ##(Debug)############################################# # E2,S2 = [[[] for _ in range(L+1)] for _ in range(2)] # E2[0].append("") ###################################################### for i in range(L): n=int(N[i]) for k in range(10): if k < n: S[i+1]+=E[i]*k S[i+1]+=S[i]*k elif k == n: E[i+1]+=E[i]*k S[i+1]+=S[i]*k else: S[i+1]+=S[i]*k E[i+1]%=MOD S[i+1]%=MOD S[i+1]+=1 #################(Debug)############################# # if k < n: # S2[i+1].extend([x+str(k) for x in E2[i]]) # S2[i+1].extend([x+str(k) for x in S2[i]]) # elif k == n: # E2[i+1].extend([x+str(k) for x in E2[i]]) # S2[i+1].extend([x+str(k) for x in S2[i]]) # else: # S2[i+1].extend([x+str(k) for x in S2[i]]) # # for i,(es,ss) in enumerate(zip(E2,S2)): # print("左から{}桁目:".format(i)) # for m,(e,s) in enumerate(zip(es,ss)): # print(" 状態={}: E={}, S={}".format(m,e,s)) ###################################################### return E[L] + S[L] ########################################################################################## MOD=10**9+7 N = list(input().strip()) # 整数を桁毎のリストとして読み込む print((digit(N)-1)%MOD)