AtCoder Beginner Contest 129 F Takahashi's Basics in Education and Learning

ABC129 F を解いた。
問題はこれ。
F - Takahashi's Basics in Education and Learning。

解説

行列累乗を使う問題。

各桁に何個あるかを間違えたので、解説をつけておく。

少し一般化した形で書きます。

$a \leq h$ を整数とし、 $d$ を正整数とする。
このとき、初項 $a$ 、公差 $d$ の数列のうち、 $h$ より小さいものの個数を求める。

以下、 $\sharp A$ により、集合 $A$ の元の個数を表すものとする。（数え上げ測度）

$\sharp\{x + d\times i | i \geq 0,\ x + d \times i < h\}$
$=\sharp\{i| i \geq 0,\ d \times i < h - x\}$
$=\max\{i+1| i \geq 0,\ d \times i< h - x\}$
$= (\lceil \frac{h-x}{d} \rceil - 1) + 1$
$= \lceil \frac{h-x}{d} \rceil$

ここで、 $\lceil b \rceil$ は $b$ 以上の最小の整数とする。
python だと、

(h-x+(d-1))//d

となります。

解答

def productMatrix(N, A, B):
    Ret = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                Ret[i][j] += A[i][k]*B[k][j]
    return Ret
def modMatrix(N, A, Q): #N×N行列のmod
    for i in range(N):
        for j in range(N):
            A[i][j] %= Q
    return

def powOfMatrix(N, X, n, Q): #N×N行列のn乗
    Ret = [[1,0,0],[0,1,0],[0,0,1]]
    power = '{:060b}'.format(n)[::-1] #log2(pow(10,18)) < 60
    for p in power:
        if p == "1":
            Ret = productMatrix(N,Ret, X)
            modMatrix(N, Ret, Q)
        X = productMatrix(N,X,X)
        modMatrix(N, X, Q)
    return Ret

def main():
    L, A, B, M = map( int, input().split())
    s = A
    ANS = [[1,0,0],[0,1,0],[0,0,1]]
    for i in range(1, 37):
        if s >= pow(10,i):
            continue
        P = [[pow(10, i, M), 0, 0], [1,1,0], [0,B,1]]
        step = (pow(10,i)-s+B-1)//B
        if L <= step:
            ANS = productMatrix(3,ANS,powOfMatrix(3,P,L,M))
            modMatrix(3,ANS,M)
            break
        ANS = productMatrix(3,ANS, powOfMatrix(3,P, step,M))
        modMatrix(3,ANS, M)
        L -= step
        s += step*B
    print( (ANS[1][0]*A + ANS[2][0])%M)

if __name__ == '__main__':
    main()

おまけ

python の関数は参照渡しなことを最近知ったので、使ってみた。
数値型以外は参照渡しらしい。これは違うっぽい。
文字型も参照渡しじゃないみたい。

今回のコードは、pypy より python のほうが速い。
何が原因か分からない。