AtCoder ARC020 C
問題リンク https://atcoder.jp/contests/arc020/tasks/arc020_3 前提となる知識 \((a + b) \bmod p = (a \bmod p) + (b \bmod p)\) \((a * b) \bmod p = (a \bmod p) * (b \bmod p)\) 解説 与えられた\(A\)を、文字列をつなげるやり方に代えて掛け算と足し算の繰り返しで構築することを考えます。問題文中の例で考えます。 はじめに\(A\)を0とする \(A\)を1000倍する \(A\)に123を足す 123 \(A\)を1000倍する \(A\)に123を足す 123123 \(A\)を10倍する \(A\)に4を足す 1231234 \(A\)を10倍する \(A\)に4を足す 12312344 \(A\)を100倍する \(A\)に56を足す 1231234456 一般的には、次の操作を行えばよいです。 変数\(V\)を用意して、これを0とする 各\(i\)について、 次を\(l_i\)回繰り返す \(V\)を10の(\(a_i\)の桁数)乗倍する \(V\)に\(a_i\)を足す 愚直に計算すると、\(L = \sum_{i=1}^N l_i\)として\(L\)回の操作が必要になり、これは間に合いません。同じ操作を何度も繰り返しているので、これを何とかまとめて計算する方法を考えていきましょう。 例えば繰り返し部分のうち「\(V\)に\(a_i\)を足す」がなければ、\(i\)回目の処理は\(V\)に10を何度か掛け算するだけになります。累乗の計算は、次のようにして高速に行うことができます。 \(x^{2p} = x^p * x^p\) \(x^{2p+1} = x * x^p * x^p\) 指数を半分にしていくことで、\(x^p\)は\(O(\log p)\)で計算できます。 問題のように掛け算と足し算が組み合わさった場合でも、「行列」を使うことで似たようなことができます。\(i\)回目の処理は、\(a_i\)の桁数を\(d_i\)として次のように書けます。 \[\begin{pmatrix} nextV \\ 1 \end{pmatrix} = \begin{pmatrix} 10^{d