結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
👑 ![]() |
提出日時 | 2021-03-05 21:59:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 248 ms / 3,000 ms |
コード長 | 1,156 bytes |
コンパイル時間 | 459 ms |
コンパイル使用メモリ | 82,328 KB |
実行使用メモリ | 98,432 KB |
最終ジャッジ日時 | 2024-10-07 01:50:55 |
合計ジャッジ時間 | 5,107 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
N=input()Mod=10**9+7DP=[[[0]*100,[0]*100] for _ in range(len(N)+1)]DP[0][0][1]=1for i,m in enumerate(N,1):m=int(m)Df,Dt=DP[i]Ef,Et=DP[i-1]#True -> Truefor s in range(1,10):for r in range(100):Dt[(r*s)%100]+=Et[r]#False -> Truefor s in range(1,m):for r in range(100):Dt[(r*s)%100]+=Ef[r]#False -> Falseif m>0:for r in range(100):Df[(r*m)%100]+=Ef[r]for r in range(100):Dt[r]%=ModDf[r]%=Modalpha=(DP[-1][0][0]+DP[-1][1][0])%Mod#========DP=[[[0]*3 for _ in range(3)] for _ in range(len(N))]DP[0][0][0]=1for i in range(1,len(N)):D=DP[i]E=DP[i-1]for s in range(1,10):p=q=0if s==2 or s==6:p=1elif s==4:p=2elif s==8:p=3if s==5:q=1for t in range(3):for u in range(3):D[min(t+p,2)][min(u+q,2)]+=E[t][u]for t in range(3):for u in range(3):D[t][u]%=Modbeta=0for i in range(1,len(N)):beta+=DP[i][2][2]print((alpha+beta)%Mod)