Problem p03016 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B,mod):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)])%mod for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():

    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    L,A,B,M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    mod=M
    ans=0
    cur=0
    a10=1
    cs=A
    for alp in range(18):
        l=a10-A-1
        r=a10*10-A-1
        a10*=10

        if r<0:
            
            continue
        if l<0:
            lb=0
        else:
            lb=l//B+1
        rb=r//B+1
        #printe(rb)
        rrb=min(L,rb)
        n=(rrb-lb)
        mat=[[0]*3 for _ in range(3)]
        mat[0][0]=pow(10,alp+1,mod)
        mat[0][1]=1
        mat[1][1]=1
        mat[1][2]=B%mod
        mat[2][2]=1
        v=[ans,cs,1]
        tot=[[0]*3 for _ in range(3)]
        for i in range(3):tot[i][i]=1
        #printe(mat)
        for j in range(n.bit_length()):
            if (n>>j)&1:
                tot=matmat(mat,tot,M)
            mat=matmat(mat,mat,M)
            #printe(j,mat)

        x=matvec(tot,v)
        ans=x[0]%mod
        cs=x[1]%mod
        
        if rb>L:
            break
        


    print(ans)



if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
import numpy as np
def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B,mod):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)])%mod for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():

    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    L,A,B,M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    mod=M
    ans=0
    cur=0
    a10=1
    cs=A
    for alp in range(18):
        l=a10-A-1
        r=a10*10-A-1
        a10*=10

        if r<0:
            
            continue
        if l<0:
            lb=0
        else:
            lb=l//B+1
        rb=r//B+1
        #printe(rb)
        rrb=min(L,rb)
        n=(rrb-lb)
        mat=np.zeros((3,3),dtype='i8')
        mat[0][0]=pow(10,alp+1,mod)
        mat[0][1]=1
        mat[1][1]=1
        mat[1][2]=B%mod
        mat[2][2]=1
        v=np.array([ans,cs,1],'i8')
        tot=np.eye(3,dtype='i8')
        #printe(mat)
        for j in range(n.bit_length()):
            if (n>>j)&1:
                tot=mat@tot%M
            mat=mat@mat%M
            #printe(j,mat)

        x=tot@v
        ans=x[0]%mod
        cs=x[1]%mod
        
        if rb>L:
            break
        


    print(ans)



if __name__ == "__main__":
    main()