結果
問題 |
No.1417 100の倍数かつ正整数(2)
|
ユーザー |
![]() |
提出日時 | 2021-03-05 23:28:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 98 ms / 3,000 ms |
コード長 | 2,803 bytes |
コンパイル時間 | 541 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 77,952 KB |
最終ジャッジ日時 | 2024-10-07 05:16:26 |
合計ジャッジ時間 | 3,500 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
import sys input = sys.stdin.readline N=input().strip() mod=10**9+7 LEN=len(N) DP1=[0]*(LEN+1) DP2=[0]*(LEN+1) DP4=[0]*(LEN+1) DP5=[0]*(LEN+1) DP10=[0]*(LEN+1) DP20=[0]*(LEN+1) DP25=[0]*(LEN+1) DP50=[0]*(LEN+1) DP100=[0]*(LEN+1) F=1 for i in range(LEN): x=int(N[i]) DP1[i]=DP1[i-1]*4%mod DP2[i]=(DP2[i-1]*4+DP1[i-1]*2)%mod DP4[i]=(DP4[i-1]*8+DP1[i-1]*2+DP2[i-1]*4)%mod DP5[i]=(DP5[i-1]*4+DP1[i-1])%mod DP10[i]=(DP10[i-1]*4+DP2[i-1]+DP5[i-1]*2)%mod DP20[i]=(DP20[i-1]*8+DP4[i-1]+DP5[i-1]*2+DP10[i-1]*4)%mod DP25[i]=(DP25[i-1]*5+DP5[i-1])%mod DP50[i]=(DP50[i-1]*5+DP10[i-1]+DP25[i-1]*2)%mod DP100[i]=(DP100[i-1]*9+DP20[i-1]+DP50[i-1]*4+DP25[i-1]*2)%mod if i>=1: for j in range(1,10): if j%5==0: DP5[i]+=1 elif j%4==0: DP4[i]+=1 elif j%2==0: DP2[i]+=1 else: DP1[i]+=1 for j in range(1,x): if F==100: DP100[i]+=1 elif F==50: if j%2==0: DP100[i]+=1 else: DP50[i]+=1 elif F==25: if j%4==0: DP100[i]+=1 elif j%2==0: DP50[i]+=1 else: DP25[i]+=1 elif F==20: if j%5==0: DP100[i]+=1 else: DP20[i]+=1 elif F==10: if j%5==0: DP50[i]+=1 elif j%2==0: DP20[i]+=1 else: DP10[i]+=1 elif F==5: if j%5==0: DP25[i]+=1 elif j%4==0: DP20[i]+=1 elif j%2==0: DP10[i]+=1 else: DP5[i]+=1 elif F==4: if j%5==0: DP20[i]+=1 else: DP4[i]+=1 elif F==2: if j%5==0: DP10[i]+=1 elif j%2==0: DP4[i]+=1 else: DP2[i]+=1 elif F==1: if j%5==0: DP5[i]+=1 elif j%4==0: DP4[i]+=1 elif j%2==0: DP2[i]+=1 else: DP1[i]+=1 if x==0: F=0 elif x%5==0: if F%25==0: True else: F*=5 elif x%4==0: if F%4==0: True elif F%2==0: F*=2 else: F*=4 elif x%2==0: if F%4==0: True else: F*=2 #print(DP1[i],DP2[i],DP4[i],DP5[i],DP10[i],DP20[i],DP25[i],DP50[i],DP100[i],F) ANS=DP100[-2] if F==100: print((ANS+1)%mod) else: print(ANS%mod)