ABC129F Takahashi's Basics in Education and Learning

問題

F - Takahashi's Basics in Education and Learning

等差数列がある。これを文字通りに左から連結した数字の mod はいくつになるか。

気持ち

そのままだと扱いにくい。「連結」の操作は桁数さえ決まっていればなんとかなる。例えば桁数の数字を連結するなら、連結する前の答えに対し、

が答えになる。

こんな感じで考えると、数列を桁数ごとに分けて考えるのは自然である。 桁数を固定するとグッと解きやすくなる。実際桁をに固定したのち、オフセットを後でかけるとして、 、初項、項とすると、

を計算すれば良いことがわかる。これは例えばとに項を分けると等比数列の性質を利用すればいい高校数学問題に帰着する。よし、解けた！

...と思うのだが、実はこれだとWAをいただいてしまう。この考えだと詰めが甘い。等比数列の公式はご存知の通り(?)

となるので、で割る操作が必要になるのである。ところが今は法であるが素数とは限らないため、逆元が存在しないかもしれない。この問題の邪悪ポイントである。

そうなると等比数列の公式は使うことができない。でも漸化式の決まった数列の要素を高速に求める手法を我々は知っている。そう、行列累乗である。 つまりさっきのをうまいこと行列の形で書ければ...という気持ちになる。

ここまで行ければもう答えは出たようなものである。遷移はベクトルに対して考えれば良い。

ACコード

Submission #19568265 - AtCoder Beginner Contest 129

ちょっと汚いけど勘弁(ライブラリ省略)

import sys
input = sys.stdin.buffer.readline

def solve(L, A, B, mod):
    maxdig = len(str(A+B*(L-1)))
    alreadySelected = 1
    ans = 0
    for c in reversed(range(1, maxdig+1)):
        imax = min((10**c-A+B-1)//B-1, L-1)
        imin = max((10**(c-1)-A+B-1)//B, 0)

        a0 = A+B*imin
        d = B
        r = 10**c % mod
        n = imax - imin + 1
        if n <= 0: continue
        mat = [
            [r, 1, 0],
            [0, 1, d],
            [0, 0, 1]
        ]
        pmat = power_mat(mat, n, mod)
        score = a0 * pmat[0][1] + pmat[0][2]
        score = (score * alreadySelected) % mod
        ans = (ans + score) % mod
        alreadySelected = alreadySelected * pow(10, n*c, mod) % mod

    return ans

L, A, B, mod = map(int, input().rstrip().split())
print(solve(L, A, B, mod))

感想

modが素数じゃないの邪悪すぎる、と思ったがそれも含めてこの難易度なのかと思うと納得する。考察の段階でちゃんと細かいところまで詰めないといけない良い例。