【今日の精進】ABC129F - Takahashi's Basics in Education and Learning

毎日格上の問題を倒すやつの64日目です。

問題リンク

atcoder.jp

問題概要

項の、初項が で公差が である等差数列をつなげたものを数として解釈し、 で割ったあまりを求めてね。

解法

各桁数ごとに考えます。

そうすると、 倍して何かを足すことを繰り返すと解釈できます。

足す数も等差数列なので、以下のような行列を累乗すると解釈することができます。

また、それぞれの桁数の境目は二分探索で容易に求められます。

提出コード

def matrix_mul(a,b,MOD=None):
    ret=[[0]*len(b[0]) for i in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            for k in range(len(b)):
                ret[i][j]+=a[i][k]*b[k][j]
            if MOD:
                ret[i][j]%=MOD
    return ret

def matrix_pow(x,p,MOD=None):
    if p==1:
        return x
    if p%2==1:
        return matrix_mul(matrix_pow(x,p-1,MOD),x,MOD)
    half=matrix_pow(x,p//2,MOD)
    return matrix_mul(half,half,MOD)

L,A,B,M=map(int,input().split())
ans=0
pos=0
for i in range(1,20):
    if A+pos*B>=10**i:
        continue
    ok=pos
    ng=L
    while ng-ok>1:
        mid=(ok+ng)//2
        if A+mid*B<10**i:
            ok=mid
        else:
            ng=mid
    aft=matrix_pow([[10**i,1,0],[0,1,B],[0,0,1]],ng-pos,M)[0]
    ans=aft[0]*ans+aft[1]*(A+pos*B)+aft[2]
    pos=ng
    ans%=M
    if pos==L:
        break
print(ans)

Submission #47834302 - AtCoder Beginner Contest 129

解法

自然な行列階乗でよかった