Problem:


Score : 600 points

Problem Statement
Q tuples of integers (L_i, A_i, B_i, M_i). For each tuple, answer the following question. -->

There is an arithmetic progression with L terms: s_0, s_1, s_2, ... , s_{L-1}.

The initial term is A, and the common difference is B. That is, s_i = A + B \times i holds.

Consider the integer obtained by concatenating the terms written in base ten without leading zeros. For example, the sequence 3, 7, 11, 15, 19 would be concatenated into 37111519. What is the remainder when that integer is divided by M?

Constraints

All values in input are integers.

1 \leq L, A, B < 10^{18}

2 \leq M \leq 10^9

All terms in the arithmetic progression are less than 10^{18}.

Input

Input is given from Standard Input in the following format:

L A B M

Output

Print the remainder when the integer obtained by concatenating the terms is divided by M.

Sample Input 1

5 3 4 10007

Sample Output 1

5563

Our arithmetic progression is 3, 7, 11, 15, 19, so the answer is 37111519 mod 10007, that is, 5563.

Sample Input 2

4 8 1 1000000

Sample Output 2

891011

Sample Input 3

107 10000000000007 1000000000000007 998244353

Sample Output 3

39122908



Sample input:
5 3 4 10007


Sample output:
5563

Submission status: Wrong Answer

Solution code:
def matrix_product(X,Y,M):
    XY = [[0]*3 for _ in range(3)]

    for i in range(3):
        for j in range(3):
            for k in range(3):
                XY[i][j] += X[i][k]*Y[k][j] % M
            XY[i][j] %= M
    
    return XY

def power(X,n,M):
    res = [[1,0,0],[0,1,0],[0,0,1]]

    if n == 0: return res

    while n > 0:
        if n & 1: res = matrix_product(res,X,M)
        X = matrix_product(X,X,M)
        n //= 2
    
    return res

L, A, B, M = map(int,input().split())

X = [0,A,1]

for d in range(1,19):
    if L == 0: break

    
    l = (10**(d-1) - A + B-1) // B
    r = (10**d - A) // B
    if (10**d - A) % B == 0: r -= 1
    
    if l < 0: l = 0
    if r < 0: r = -1
    print("{0} {1}".format(l,r))

    
    C = min(r-l+1,L)
    L -= C
    print(C)

    Y = power([[10**d,0,0],[1,1,0],[0,B,1]],C,M)
    
    next_X = [0,0,0]
    for i in range(3):
        for j in range(3):
            next_X[i] += X[j] * Y[j][i] % M
        next_X[i] %= M
    X = next_X

print(X[0])

Submission status: Wrong Answer

Solution code:
# Atcoder Problem Solving
# F - Takahashi's Basics in Education and Learning
import math
L, A, D, mod = map(int, input().split())
que = []

ans = 0
# 1桁、......20桁のグループに分類する
for i in range(1, 21):
    #10**(i-1) <= A+D*(j) < 10**(i)
    lowest = max(1, math.ceil((10**(i-1)-A+D)/D))
    highest = 0
    if (10**i-A+D) % D == 0:
        highest = min((10**i-A+D)//D-1, L)
    else:
        highest = min((10**i-A+D)//D, L)
    if 1 <= lowest <= highest:
        que.append((i, lowest, highest))


def poly_sum(X, N, mod):
    # return X^N +    .... X^1+1 mod
    # O(logN)
    if N == 0:
        return 1
    if N == 1:
        return (X+1) % mod
    else:
        if N % 2 == 0:
            tmp_res = poly_sum(X, N//2, mod)
            return ((pow(X, N//2, mod)+1)*tmp_res-pow(X, N//2, mod)) % mod

        elif N % 2 != 0:
            tmp_res = poly_sum(X, N//2, mod)
            return (pow(X, N//2+1, mod)+1)*tmp_res % mod


def sum_of_poly_sum(X, N, mod):
    # return poly_sum(X,N,mod)+ poly_sum(X,N-1,mod) +poly_sum(X,N-2,mod) +.....  + poly_sum(X,1,mod) + poly_sum(X,0,mod)
    # O(logN*logN)
    if N == 0:
        return poly_sum(X, 0, mod)
    elif N == 1:
        return (poly_sum(X, 1, mod)+poly_sum(X, 0, mod)) % mod
    else:
        return ((sum_of_poly_sum(X, (N-1)//2, mod))*(pow(X, N//2+1, mod)+1)+(N//2+1)*poly_sum(X, N//2, mod)) % mod


def find_mod(length, lowest, highest, mod):
    # length 桁　の lowest 項目から highest 項目における連結巨大数のmodular
    X = pow(10, length, mod)
    if highest > lowest:
        base = (A+D*(lowest-1))*poly_sum(X, highest-lowest, mod) + \
            D*sum_of_poly_sum(X, highest-lowest - 1, mod)
    elif highest == lowest:
        base = A+D*(lowest-1)
    return base % mod


que.reverse()
digits = 0
for length, lowest, highest in que:
    ans += find_mod(length, lowest, highest, mod)*pow(10, digits, mod)
    ans %= mod
    digits += length*(highest+1-lowest)

print(ans % mod)

Submission status: Wrong Answer

Solution code:
import numpy

def power(mat:numpy.matrix, n, mod):
    ret = numpy.eye(len(mat), dtype=int)
    while n > 0:
        if n % 2 == 1:
            ret = ret @ mat % mod
        mat = mat @ mat % mod
        n //= 2
    return ret

l, a, b, m = map(int, input().split())
s_foot = a + b * (l - 1)
digit_n = len(str(s_foot))
count_digit_n = [0] * (digit_n + 1)
d = 1
for i in range(1, digit_n + 1):
    d *= 10
    x = min(d - 1, s_foot) - a
    if x < 0:
        continue
    n = x // b
    count_digit_n[i] = n + 1

for i in range(digit_n, 0, -1):
    count_digit_n[i]  -= count_digit_n[i - 1]

d = 1
x = numpy.matrix([[0], [a], [1]])
for n in count_digit_n[1:]:
    d = d * 10 % m
    if n == 0:
        continue
    mat = numpy.matrix([[d, 1, 0], [0, 1, b], [0, 0, 1]])
    x = power(mat, n, m) @ x % m
print((x[0, 0] + m) % m)

Submission status: Wrong Answer

Solution code:
import numpy

def power(mat:numpy.matrix, n, mod):
    ret = mat
    n -= 1
    while n > 0:
        if n % 2 == 1:
            ret = ret @ mat % mod
        mat = mat @ mat % mod
        n //= 2
    return ret

l, a, b, m = map(int, input().split())
s_foot = a + b * (l - 1)
digit_n = len(str(s_foot))
count_digit_n = [0] * (digit_n + 1)
d = 1
for i in range(1, digit_n + 1):
    d *= 10
    x = min(d - 1, s_foot) - a
    if x < 0:
        continue
    n = x // b
    count_digit_n[i] = n + 1

for i in range(digit_n, 0, -1):
    count_digit_n[i]  -= count_digit_n[i - 1]

d = 1
x = numpy.matrix([[0], [a], [1]])
for n in count_digit_n[1:]:
    d = d * 10 % m
    if n == 0:
        continue
    mat = numpy.matrix([[d, 1, 0], [0, 1, b], [0, 0, 1]])
    x = power(mat, n, m) @ x % m
print(x[0, 0])

Submission status: Wrong Answer

Solution code:
# 行列a*行列b
def matprod(a,b,mod):
  n=len(a)
  l=len(b)
  m=len(b[0])
  return [[sum(a[i][k]*b[k][j]for k in range(l))%mod for j in range(m)]for i in range(n)]

# 行列a^n
def matpow(a,n,mod):
  ans=[[i==j for j in range(len(a[0]))]for i in range(len(a))]
  d=a[:][:]
  while n!=0:
    if n&1:ans=matprod(d,ans,mod)
    d=matprod(d,d,mod)
    n>>=1
  return ans

def calc(x,t,i):
  mata=[[10**i,0,0],[1,1,0],[0,+b,1]]
  matx=[[x,x+b,1]]
  return matprod(matx,matpow(mata,t,m),m)[0][0]

l,a,b,m=map(int,input().split())
mind=len(str(a))
maxd=len(str(a+b*(l-1)))
ans=0
su=0
for i in range(maxd,mind-1,-1):
  mi=(0--(10**(i-1)-a)//b)*b+a
  ma=min((0--(10**i-a)//b)-1,l-1)*b+a
  co=(ma-mi)//b
  ans=(ans+pow(10,su,m)*calc(mi,co,i))%m
  su+=i*(co+1)
print(ans)

Submission status: Wrong Answer

Solution code:
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()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(19,0,-1):
        if len(str(S(left)))==k:
            right=nibutan(-1,left,k)
            sec.append((k,left,right))
            left=right
    
    def modinv(a, mod=M):
        g=gcd(a,mod)
        a//=g
        mod//=g
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    ans=0
    c=0
    for k,left,right in sec:
        C=pow(10,k,M)
        n=left-right
        ans+=(S(left)*(pow(C,n,M)-1)-B*((n-1)*pow(C,n,M)-(pow(C,n,M)-1)*modinv(C-1)+1))*modinv(C-1)*pow(10,c,M)
        ans%=M
        c+=n*k
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(19,0,-1):
        if len(str(S(left)))==k:
            right=nibutan(-1,left,k)
            sec.append((k,left,right))
            left=right
    
    def modinv(a, mod=M):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    ans=0
    c=0
    for k,left,right in sec:
        C=pow(10,k,M)
        n=left-right
        ans+=(S(left)*(pow(C,n,M)-1)-B*((n-1)*pow(C,n,M)-(pow(C,n,M)-1)*modinv(C-1)+1))*modinv(C-1)*pow(10,c,M)
        ans%=M
        c+=n*k
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    max_dig=len(str(S(L-1)))
    min_dig=len(str(S(0)))
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(max_dig,min_dig-1,-1):
        if len(str(S(left)))==k:
            right=nibutan(-1,left,k)
            sec.append((k,left,right))
            left=right
    
    def modinv(a, mod=M):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    ans=0
    c=0
    for k,left,right in sec:
        C=pow(10,k,M)
        n=left-right
        ans+=(S(left)*(pow(C,n,M)-1)-B*((n-1)*pow(C,n,M)-(pow(C,n,M)-1)*modinv(C-1)+1))*modinv(C-1)*pow(10,c,M)
        ans%=M
        c+=n*k
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    max_dig=len(str(S(L-1)))
    min_dig=len(str(S(0)))
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(max_dig,min_dig-1,-1):
        if len(str(S(left)))==k:
            right=nibutan(-1,left,k)
            sec.append((k,left,right))
            left=right
    
    def modinv(a, mod=M):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    ans=0
    c=0
    for k,left,right in sec:
        C=pow(10,k,M)
        n=left-right
        ans+=(S(left)*(pow(C,n,M)-1)*modinv(C-1)-B*((n-1)*pow(C,n,M)-(pow(C,n,M)-1)*modinv(C-1)+1)*modinv(C-1))*pow(10,c,M)
        ans%=M
        c+=n*k
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    max_dig=len(str(S(L-1)))
    min_dig=len(str(S(0)))
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(max_dig,min_dig-1,-1):
        right=nibutan(-1,left,k)
        sec.append((k,left,right))
        left=right
    
    def modinv(a, mod=M):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    ans=0
    c=0
    for k,left,right in sec:
        C=pow(10,k,M)
        n=left-right
        ans+=(S(left)*(pow(C,n,M)-1)*modinv(C-1)-B*((n-1)*pow(C,n,M)-(pow(C,n,M)-1)*modinv(C-1)+1)*modinv(C-1))*pow(10,c,M)
        ans%=M
        c+=n*k
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    sL_1=S(L-1)
    dig=len(str(sL_1))
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(dig,0,-1):
        right=nibutan(-1,left,k)
        sec.append((k,left,right))
        left=right
    
    def modinv(a, mod=M):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    ans=0
    c=0
    for k,left,right in sec:
        C=pow(10,k,M)
        n=left-right
        ans+=(S(left)*(pow(C,n,M)-1)*modinv(C-1)-B*((n-1)*pow(C,n,M)-(pow(C,n,M)-1)*modinv(C-1)+1)*modinv(C-1))*pow(10,c,M)
        ans%=M
        c+=n*k
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
l, a, b, m = map(int, input().split())
# l = 107
# a = 10000000000007  # 10**13 + 7
# b = 1000000000000007  # 10**15 + 7
# m = 998244353

s_max = a + b * (l - 1)
ten_pow = [1]
while ten_pow[-1] <= s_max:
    ten_pow.append(ten_pow[-1] * 10)
D_MAX = len(ten_pow)
d = [0] * D_MAX
for i in range(D_MAX):
    if ten_pow[i] >= a:
        d[i] = (ten_pow[i] - a) // b
        if (ten_pow[i] - a) % b == 0:
            d[i] -= 1
d[-1] = l - 1
cd = [d[i + 1] - d[i] for i in range(len(d) - 1)]
# print(ten_pow)
# print(d)
# print(cd)

y = np.array([a, a + b, 1]).T % m
for i in range(len(cd)):
    x = np.array([[ten_pow[i + 1] % m, 1, 0], [0, 1, b], [0, 0, 1]])
    x %= m
    # print(x)
    # print('y', y)
    k = cd[i]
    while k > 0:
        if k & 1:
            y = np.dot(x, y) % m
            # print('y', y)
        x = np.dot(x, x) % m
        k = k >> 1

ans = y[0]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
l, a, b, m = map(int, input().split())
# l = 107
# a = 10000000000007  # 10**13 + 7
# b = 1000000000000007  # 10**15 + 7
# m = 998244353

s_max = a + b * (l - 1)
ten_pow = [1]
while ten_pow[-1] <= s_max:
    ten_pow.append(ten_pow[-1] * 10)
D_MAX = len(ten_pow)
d = [0] * D_MAX
for i in range(D_MAX):
    if ten_pow[i] >= a:
        d[i] = (ten_pow[i] - a) // b
        if (ten_pow[i] - a) % b == 0:
            d[i] -= 1
d[-1] = l - 1
cd = [d[i + 1] - d[i] for i in range(len(d) - 1)]
# print(ten_pow)
# print(d)
# print(cd)

y = np.array([a, a + b, 1]).T % m
for i in range(len(cd)):
    x = np.array([[ten_pow[i + 1], 1, 0], [0, 1, b], [0, 0, 1]])
    x %= m
    # print(x)
    # print('y', y)
    k = cd[i]
    while k > 0:
        if k & 1:
            y = np.dot(x, y) % m
            # print('y', y)
        x = np.dot(x, x) % m
        k = k >> 1

ans = y[0]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import numpy as np
    l, a, b, m = list(map(int, readline().split()))
    d_min = len(str(a))
    d_max = len(str(a + (l - 1) * b))
    count_d = [-1] * 19

    prev = -1
    for i in range(d_min, d_max + 1):
        power = 10 ** i
        ok = 0
        ng = l + 1
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            x = a + mid * b
            if x < power:
                ok = mid
            else:
                ng = mid
        ok = min(ok, l - 1)
        count_d[i] = ok - prev
        prev = ok

    res = np.array([0, a, 1], dtype="int64")

    for i in range(19):
        count = count_d[i]
        if count == -1:
            continue
        mat = np.array([[10 ** i, 0, 0],
                        [1, 1, 0],
                        [0, b, 1]], dtype="int64")
        mat = np.mod(mat, m)
        cur = np.eye(3, dtype="int64")
        count_bit = format(count, "b")
        for bit in count_bit[::-1]:
            if bit == "1":
                cur = np.dot(cur, mat)
                cur = np.mod(cur, m)
            mat = np.dot(mat, mat)
            mat = np.mod(mat, m)
        res = np.dot(res, cur)
        res = np.mod(res, m)

    print(res[0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil
from functools import lru_cache
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**6)

@lru_cache(maxsize=1024)
def power(n, mod): # 10 ** n % mod
    return pow(10, n, mod)

@lru_cache(maxsize=1024)
def f(L, d, mod):
    if L == 0: val = 0
    elif L == 1: val = 1
    elif L % 2 == 0:
        val = ( f(L // 2, d, mod) * power(L * d // 2, mod) + f(L // 2, d, mod) ) % mod
    elif L % 2 != 0:
        val = ( f(L - 1, d, mod) * power(d, mod) + 1 ) % mod
    #print("f({}, {})={}".format(L, d, val))
    return val

@lru_cache(maxsize=1024)
def g(L, d, B, mod):
    if L == 0: val = 0
    elif L == 1: val = 0
    elif L % 2 == 0:
        val = ( g(L // 2, d, B, mod) * power(L * d // 2, mod) + g(L // 2, d, B, mod) + (B * L // 2) * f(L // 2, d, mod) ) % mod
    elif L % 2 != 0:
        val = ( g(L - 1, d, B, mod) * power(d, mod) + B * (L - 1) ) % mod
    #print("g({}, {})={}".format(L, d, val))
    return val

def main():
    L, A, B, mod = map(int, input().split())

    """
    数列の桁が変わっていくのが面倒だが、桁数dの数列の要素の個数は
        (10^(d+1)未満の要素の個数) - (10^d未満の要素の個数)
    で簡単に求まるので、とりあえず桁数は同じで考えて良い

    このとき求めるのは
        \Sum_{i=0}^{L-1} (A+Bi) * 10^{d(L-i-1)}
    これは分解すれば
        f(L) = \Sum_{i=0}^{L-1} 10^{di}
        g(L) = \Sum_{i=0}^{L-1} Bi * 10^{d(L-i-1)}
    の線形和(= A * f(L) + g(L))として求まる。

    前者については
        f(L + 1) = f(L) * 10^d + 1
        f(L * 2) = f(L) * 10^{Ld} + f(L)
    が成り立つので二分法によりO(log^2 L)で求まる（f(18)->f(9)->f(8)->f(4)->f(2)->f(1)みたいに）

    後者については
        g(L + 1) = g(L) * 10^d
        g(L * 2) = g(L) * 10^{Ld} + g(L) + (BL * f(L))
    なのでやはり同様に二分法が可能でO(log^3 L)で計算可能。
    """

    # まずは桁数で区切る
    initial = [0] * 19 # initial[d] = (数列の項でd桁にはじめてなる項の値)
    number = [0] * 19  # number[d] = (数列の項でd桁である物が何個存在するか)

    for d in range(len(str(A)), 19):
        i = max(0, ceil((10**(d - 1) - A) / B))
        initial[d] = A + B * i
        if (10**d - A) % B == 0:
            number[d] = (10**d - A) // B - i
        else:
            number[d] = (10**d - A) // B - i + 1
        if number[d] == 0:
            initial[d] = 0
    
    max_len = len(str(A + B * (L - 1)))
    exceeded_num = sum(number[:(max_len + 1)]) - L
    number[max_len] -= exceeded_num
    initial[(max_len + 1):] = [0] * (18 - max_len)
    number[(max_len + 1):] = [0] * (18 - max_len)
    #print("initial={}".format(initial))
    #print("number={}".format(number))
    
    # 各dについて上述の値を計算
    ans = 0
    digits = 0
    for d in range(18, 0, -1):
        a = initial[d]
        l = number[d]
        val = (a * f(l, d, mod) + g(l, d, B, mod)) * power(digits, mod)
        val %= mod
        ans += val
        ans %= mod
        digits += d * l
        #print("d={}->val={}".format(d, val))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil
from functools import lru_cache
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**6)

@lru_cache(maxsize=10**3)
def power(n, mod): # 10 ** n % mod
    return pow(10, n, mod)

@lru_cache(maxsize=10**3)
def f(L, d, mod):
    if L == 0: val = 0
    elif L == 1: val = 1
    elif L % 2 == 0:
        val = ( f(L // 2, d, mod) * power(L * d // 2, mod) + f(L // 2, d, mod) ) % mod
    elif L % 2 != 0:
        val = ( f(L - 1, d, mod) * power(d, mod) + 1 ) % mod
    #print("f({}, {})={}".format(L, d, val))
    return val

@lru_cache(maxsize=10**3)
def g(L, d, B, mod):
    if L == 0: val = 0
    elif L == 1: val = 0
    elif L % 2 == 0:
        val = ( g(L // 2, d, B, mod) * power(L * d // 2, mod) + g(L // 2, d, B, mod) + (B * L // 2) * f(L // 2, d, mod) ) % mod
    elif L % 2 != 0:
        val = ( g(L - 1, d, B, mod) * power(d, mod) + B * (L - 1) ) % mod
    #print("g({}, {})={}".format(L, d, val))
    return val

def main():
    L, A, B, mod = map(int, input().split())

    """
    数列の桁が変わっていくのが面倒だが、桁数dの数列の要素の個数は
        (10^(d+1)未満の要素の個数) - (10^d未満の要素の個数)
    で簡単に求まるので、とりあえず桁数は同じで考えて良い

    このとき求めるのは
        \Sum_{i=0}^{L-1} (A+Bi) * 10^{d(L-i-1)}
    これは分解すれば
        f(L) = \Sum_{i=0}^{L-1} 10^{di}
        g(L) = \Sum_{i=0}^{L-1} Bi * 10^{d(L-i-1)}
    の線形和(= A * f(L) + g(L))として求まる。

    前者については
        f(L + 1) = f(L) * 10^d + 1
        f(L * 2) = f(L) * 10^{Ld} + f(L)
    が成り立つので二分法によりO(log^2 L)で求まる（f(18)->f(9)->f(8)->f(4)->f(2)->f(1)みたいに）

    後者については
        g(L + 1) = g(L) * 10^d
        g(L * 2) = g(L) * 10^{Ld} + g(L) + (BL * f(L))
    なのでやはり同様に二分法が可能でO(log^3 L)で計算可能。
    """

    # まずは桁数で区切る
    initial = [0] * 19 # initial[d] = (数列の項でd桁にはじめてなる項の値)
    number = [0] * 19  # number[d] = (数列の項でd桁である物が何個存在するか)

    for d in range(len(str(A)), 19):
        i = max(0, ceil((10**(d - 1) - A) / B))
        initial[d] = A + B * i
        if (10**d - A) % B == 0:
            number[d] = max(0, (10**d - A) // B) - i
        else:
            number[d] = max(0, (10**d - A) // B) - i + 1
    
    max_len = len(str(A + B * (L - 1)))
    exceeded_num = sum(number[:(max_len + 1)]) - L
    number[max_len] -= exceeded_num
    initial[(max_len + 1):] = [0] * (18 - max_len)
    number[(max_len + 1):] = [0] * (18 - max_len)
    #print("initial={}".format(initial))
    #print("number={}".format(number))
    
    # 各iについて上述の値を計算
    ans = 0
    digits = 0
    for d in range(18, 0, -1):
        a = initial[d]
        l = number[d]
        val = (a * f(l, d, mod) + g(l, d, B, mod)) * power(digits, mod)
        val %= mod
        ans += val
        ans %= mod
        digits += d * l
        #print("d={}->val={}".format(d, val))
    print(ans)

if __name__ == "__main__":
    main()

"""
異なるdに移った時10**x倍して桁ずらすの忘れてる！。
"""

Submission status: Wrong Answer

Solution code:
L, A, B, M = map(int, input().split())
f = [0 for i in range(20)]
def doubling(n, m, mod):
  y = 1
  base = n
  while m != 0:
    if m % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    m //= 2
  return y
def factorization(n):
  if n == 1:
    return {1: 1}
  else:
    p = 2
    tmp = n
    D = {}
    while n != 1:
      i = 0
      while n % p == 0:
        i += 1
        n //= p
      if i != 0:
        D[p] = i
      p += 1
      if p * p > tmp and n != 1:
        D[n] = 1
        break
    return D
def Torshent(n):
  S = n
  dic = factorization(n)
  for i in dic:
    S //= i
    S *= (i - 1)
  return S

d = 1
for i in range(20):
  l, r = max(-1, (d - A - 1) // B), max(-1, (10*d - A - 1) // B)
  if i == 0:
    f[i] = min(r, L-1) - min(l, L-1)
  else:
    f[i] = f[i-1] + min(r, L-1) - min(l, L-1)
  d *= 10

N = 0
l, r = 0, 0
for i in range(20):
  r = f[i]
  N = N * doubling(10, (i+1)*(r-l), M)
  prod = (A + B * l) * (doubling(10, (i+1)*(r-l), M) - 1)
  prod *= doubling(doubling(10, (i+1), M) - 1, Torshent(M)-1, M)
  prod %= M
  N += prod
  N %= M
  d1 = doubling(10, (i+1)*(r-l), M)
  d2 = doubling(10, (i+1), M)
  prod = B * ((d1 - 1) - (r - l) * (d2 - 1))
  prod *= doubling(d2 - 1, Torshent(M)-1, M)
  prod *= doubling(d2 - 1, Torshent(M)-1, M)
  prod %= M
  N += prod
  N %= M
  l = f[i]
print(N)

Submission status: Wrong Answer

Solution code:
l,a,b,m=map(int,input().split())

x=[]
idx=-1
for i in range(1,19):
    buf=(10**i-1-a)//b
    if idx>=buf:
        continue
    if buf>=l:
        x.append((l-1,i))
        break
    if buf<0:
        continue
    x.append((buf,i))
    if buf==l-1:
        break
    idx=buf
def egcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    if a == 0:
        return (b, 0, 1)
    else:
        b_div_a, b_mod_a = divmod(b, a)
        g, x, y = egcd(b_mod_a, a)
        return (g, y - b_div_a * x, x)
xdiv=[0]*19
for i in range(19):
    _,buf,_=egcd(pow(10,i,m)-1,m)
    xdiv[i]=buf%m

idx=-1
count=0
y=[]
#print(x)
for item,n in x:
    end=(a+b*(idx+1))%m
    init=(a+b*item)%m
    N=item-idx
    #print(init,end)
    if N>=2:
        inc=end*pow(10,N*n,m)-init+b*(pow(10,n,m))*(pow(10,n*(N-1),m)-1)*(xdiv[n])
        inc%=m
        inc*=xdiv[n]
        inc%=m
    else:
        inc=init
    y.append((inc,n,(item-idx)))
    idx=item
#print(y)
ll=len(y)
for i in range(ll):
    f,g,h=y[i]
    if i!=0:
        count*=pow(10,g*h,m)
        count%=m
    count+=f
    count%=m
print(count)

Submission status: Wrong Answer

Solution code:
l,a,b,m=map(int,input().split())

x=[]
for i in range(1,19):
    buf=(10**i-1-a)//b
    if buf>=l:
        x.append((l-1,i))
        break
    if buf<1:
        continue
    x.append((buf,i))
def egcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    if a == 0:
        return (b, 0, 1)
    else:
        b_div_a, b_mod_a = divmod(b, a)
        g, x, y = egcd(b_mod_a, a)
        return (g, y - b_div_a * x, x)
xdiv=[0]*19
for i in range(19):
    _,buf,_=egcd(pow(10,i,m)-1,m)
    xdiv[i]=buf%m

idx=-1
count=0
y=[]
for item,n in x:
    end=(a+b*(idx+1))
    init=(a+b*item)
    #print(init,end)
    inc=end*pow(10,(item-idx)*n,m)-init+b*(pow(10,n,m))*(pow(10,n*((item-idx)-1),m)-1)*(xdiv[n])
    inc%=m
    inc*=xdiv[n]
    inc%=m
    y.append((inc,n,(item-idx)))
    idx=item
#print(y)
ll=len(y)
for i in range(ll):
    f,g,h=y[i]
    if i!=0:
        count*=pow(10,g*h,m)
        count%=m
    count+=f
    count%=m
print(count)