結果

問題 No.1417 100の倍数かつ正整数(2)
ユーザー persimmon-persimmonpersimmon-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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,848 KB
testcase_01 AC 37 ms
53,352 KB
testcase_02 AC 60 ms
68,568 KB
testcase_03 AC 37 ms
52,332 KB
testcase_04 AC 36 ms
53,572 KB
testcase_05 AC 37 ms
53,588 KB
testcase_06 AC 38 ms
54,168 KB
testcase_07 AC 38 ms
52,292 KB
testcase_08 AC 37 ms
52,636 KB
testcase_09 AC 36 ms
52,884 KB
testcase_10 AC 40 ms
52,856 KB
testcase_11 AC 37 ms
52,612 KB
testcase_12 AC 44 ms
61,956 KB
testcase_13 AC 45 ms
61,992 KB
testcase_14 AC 50 ms
64,140 KB
testcase_15 AC 53 ms
66,292 KB
testcase_16 AC 56 ms
67,632 KB
testcase_17 AC 55 ms
67,848 KB
testcase_18 AC 57 ms
67,980 KB
testcase_19 AC 60 ms
68,724 KB
testcase_20 AC 60 ms
69,396 KB
testcase_21 AC 62 ms
69,772 KB
testcase_22 AC 62 ms
69,992 KB
testcase_23 AC 62 ms
70,600 KB
testcase_24 AC 60 ms
69,372 KB
testcase_25 AC 62 ms
70,288 KB
testcase_26 AC 61 ms
69,256 KB
testcase_27 AC 63 ms
69,820 KB
testcase_28 AC 61 ms
69,628 KB
testcase_29 AC 62 ms
69,888 KB
testcase_30 AC 90 ms
76,004 KB
testcase_31 AC 85 ms
76,696 KB
testcase_32 AC 122 ms
77,516 KB
testcase_33 AC 110 ms
76,560 KB
testcase_34 AC 110 ms
76,160 KB
testcase_35 AC 114 ms
76,644 KB
testcase_36 AC 116 ms
76,544 KB
testcase_37 AC 122 ms
76,416 KB
testcase_38 AC 111 ms
76,680 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