結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
|
提出日時 | 2021-09-11 10:03:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 216 ms / 3,000 ms |
コード長 | 1,029 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,180 KB |
実行使用メモリ | 82,660 KB |
最終ジャッジ日時 | 2024-06-22 16:40:48 |
合計ジャッジ時間 | 4,830 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
N=input() DP=[[[0]*10 for _ in range(2)] for _ in range(len(N)+1)] # DP[i][j][k]=上からi桁目まで決めてj=0ならN未満,j=1ならNと等しいかものやつ # k=0~8は2でk//3回,5でk%3回割れる,k=9は今まで全部0を選んできた DP[0][1][9]=1 mod=10**9+7 for i in range(len(N)): n=int(N[i]) for j in range(2): for k in range(10): for x in range(10): j2,k2=j,k if j2 and x>n: continue if k2<=8 and x==0: continue if x==2 or x==6: if k2<=5: k2+=3 elif k2==9: k2=3 elif x==4 or x==8: if k2<=2: k2+=6 elif k2<=5: k2+=3 elif k2==9: k2=6 elif x==5: if k2==9: k2=1 elif k2%3!=2: k2+=1 elif x!=0: if k2==9: k2=0 if x<n: j2=0 DP[i+1][j2][k2]=(DP[i+1][j2][k2]+DP[i][j][k])%mod print((DP[-1][0][8]+DP[-1][1][8])%mod) #print(DP)