結果

問題 No.1417 100の倍数かつ正整数(2)
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-03-11 13:52:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 135 ms / 3,000 ms
コード長 1,349 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 77,568 KB
最終ジャッジ日時 2024-04-21 04:02:57
合計ジャッジ時間 4,801 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,352 KB
testcase_01 AC 37 ms
52,864 KB
testcase_02 AC 67 ms
69,120 KB
testcase_03 AC 37 ms
52,480 KB
testcase_04 AC 38 ms
52,224 KB
testcase_05 AC 39 ms
52,224 KB
testcase_06 AC 38 ms
52,352 KB
testcase_07 AC 40 ms
52,736 KB
testcase_08 AC 39 ms
52,480 KB
testcase_09 AC 40 ms
52,992 KB
testcase_10 AC 40 ms
52,608 KB
testcase_11 AC 39 ms
52,480 KB
testcase_12 AC 49 ms
60,416 KB
testcase_13 AC 49 ms
60,672 KB
testcase_14 AC 55 ms
63,616 KB
testcase_15 AC 61 ms
65,152 KB
testcase_16 AC 64 ms
66,176 KB
testcase_17 AC 65 ms
67,328 KB
testcase_18 AC 66 ms
67,840 KB
testcase_19 AC 68 ms
68,096 KB
testcase_20 AC 67 ms
68,480 KB
testcase_21 AC 68 ms
68,992 KB
testcase_22 AC 72 ms
68,992 KB
testcase_23 AC 70 ms
69,376 KB
testcase_24 AC 68 ms
68,992 KB
testcase_25 AC 69 ms
69,248 KB
testcase_26 AC 69 ms
68,992 KB
testcase_27 AC 69 ms
69,504 KB
testcase_28 AC 69 ms
69,760 KB
testcase_29 AC 69 ms
69,632 KB
testcase_30 AC 100 ms
76,936 KB
testcase_31 AC 96 ms
76,416 KB
testcase_32 AC 135 ms
77,568 KB
testcase_33 AC 125 ms
76,948 KB
testcase_34 AC 117 ms
76,800 KB
testcase_35 AC 122 ms
76,784 KB
testcase_36 AC 123 ms
76,628 KB
testcase_37 AC 130 ms
76,848 KB
testcase_38 AC 121 ms
76,800 KB
権限があれば一括ダウンロードができます

ソースコード

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