結果

問題 No.1417 100の倍数かつ正整数(2)
コンテスト
ユーザー persimmon-persimmon
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0