ABC129 F. Takahashi's Basics in Education and Learning

問題

長さLの等差数列があり、初項はA、公差はBで与えられる。
この数列の項を順につなげてできる整数を考える。
例えば、3,7,11,15,19という数列の場合は、37111519という整数になる。
この整数をMで割ったあまりを答えよ。

制約

• 1 <= L, A, B < 10^18
• 2 <= M <= 10^9
• 数列の要素はすべて10^18未満

解法

数列の桁に注目すると、ある桁dの区間では数列の値を10^d倍ずつしていったものになっていることがわかる。

数列の要素の桁がdであるような区間について考える。
要素の増え方と10^d倍ずつしていくので、後ろに要素を付け加えていくようなイメージで考えると、ある要素までの計算結果をYとして、今考えている要素がxだとしたら
(Y, x) -> (Y * 10^d + x, x + B)
で更新される。
これをN回繰り返したあとのYを考えればよく、これは行列累乗を使うと、
{( (10^d, 1, 0), (0, 1, B), (0, 0, 1) )^N} * (Y, x, 1)^T
の形で書ける。(行列累乗で数列の一般項を求めるのはよくある)

最初、(Y, x, 1) = (0, A, 1)として、桁dの区間を1,2,3,4,...と連続的に処理していけば答えが求められる。
桁がdであるような区間は二分探索などで求めれば良い。

(行列累乗時に18桁*18桁のような計算がでてしまうが__uint128_tなどを使ってオーバーフローしないようにするMが10^9程度なので、普通に掛け算する前にmodをとっておけば良い。)