結果
問題 | No.1407 Kindness |
ユーザー |
|
提出日時 | 2021-02-26 21:49:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 1,912 bytes |
コンパイル時間 | 473 ms |
コンパイル使用メモリ | 82,236 KB |
実行使用メモリ | 81,792 KB |
最終ジャッジ日時 | 2024-10-02 14:27:29 |
合計ジャッジ時間 | 3,809 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
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] = 1S[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]*kS[i+1]+=S[i]*kelif k == n:E[i+1]+=E[i]*kS[i+1]+=S[i]*kelse:S[i+1]+=S[i]*kE[i+1]%=MODS[i+1]%=MODS[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+7N = list(input().strip()) # 整数を桁毎のリストとして読み込むprint((digit(N)-1)%MOD)