結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2022-11-23 16:40:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,408 ms / 3,000 ms |
コード長 | 793 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,096 KB |
実行使用メモリ | 114,808 KB |
最終ジャッジ日時 | 2024-09-24 20:35:37 |
合計ジャッジ時間 | 11,154 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
N = input()mod = 10**9+7NN = str(N)L = len(NN)# dp[i][j][k][l]:i桁目まで決めた時に,j:未満フラッグ,k:leading zero, l:mod100dp = [[[[0]*100 for _ in range(2)] for _ in range(2)] for _ in range(L+1)]dp[0][0][1][1] = 1for i in range(L):D = int(NN[i])for less_f in range(2):for leading_f in range(2):for m in range(100):for d in range(10 if less_f else D+1):# 正整数じゃなくなるif leading_f==0 and d==0:continuedp[i+1][less_f or (d<D)][leading_f and d==0][(m*d)%100 if d!=0 else m] += dp[i][less_f][leading_f][m]dp[i+1][less_f or (d<D)][leading_f and d==0][(m*d)%100 if d!=0 else m] %= modprint((dp[-1][0][0][0]+dp[-1][1][0][0])%mod)