結果
問題 |
No.1417 100の倍数かつ正整数(2)
|
ユーザー |
|
提出日時 | 2021-03-11 13:52:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 122 ms / 3,000 ms |
コード長 | 1,349 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 81,676 KB |
実行使用メモリ | 77,516 KB |
最終ジャッジ日時 | 2024-10-13 02:26:23 |
合計ジャッジ時間 | 3,912 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
nary=list(map(int,list(input()))) m=len(nary) mod=10**9+7 # 100=2*2*5*5 # 2が0,1,2個、5が0,1,2個 dp0=[[0]*3 for _ in range(3)] # ちょうどnで--の個数 dp1=[[0]*3 for _ in range(3)] # 1以上n未満で--の個数 d=[None] for num in range(1,10): cnt2=0 while num%2==0: num//=2 cnt2+=1 cnt5=0 while num%5==0: num//=5 cnt5+=1 d.append([min(2,cnt2),min(2,cnt5)]) n=nary[0] cnt2,cnt5=d[n] dp0[cnt2][cnt5]=1 for ni in range(1,n): cnt2i,cnt5i=d[ni] dp1[cnt2i][cnt5i]+=1 for i in range(1,m): ndp0=[[0]*3 for _ in range(3)] ndp1=[[0]*3 for _ in range(3)] n=nary[i] if n>0: cnt2,cnt5=d[n] # ちょうどnからの遷移 for u in range(3): for v in range(3): if dp0[u][v]==0:continue ndp0[min(2,u+cnt2)][min(2,v+cnt5)]+=dp0[u][v] for ni in range(1,n): cnt2i,cnt5i=d[ni] ndp1[min(2,u+cnt2i)][min(2,v+cnt5i)]+=dp0[u][v] # 1以上n未満からの遷移 for ni in range(1,10): cnt2i,cnt5i=d[ni] for u in range(3): for v in range(3): if dp1[u][v]==0:continue ndp1[min(2,u+cnt2i)][min(2,v+cnt5i)]+=dp1[u][v] ndp1[min(2,u+cnt2i)][min(2,v+cnt5i)]%=mod # 無からの遷移 for ni in range(1,10): cnt2i,cnt5i=d[ni] ndp1[cnt2i][cnt5i]+=1 dp0,dp1=ndp0,ndp1 print((dp0[2][2]+dp1[2][2])%mod)