ARC 020 C - A mod B Problem

• 問題
• AC

整数$a$の10進表示を$p$個並べてできた数を$(a)_p$と書くことにし、$a$の10進表示の長さを$d(a)$とする。$(a)_p \mod B$は繰り返し二乗法の要領で計算できる:
$(a)_p = \begin{cases} 0 \qquad & (p= 0) \\ (a)_{p-1} \cdot 10^{d(a)} + a \qquad & (pが奇数) \\ (a)_{p/2} \cdot 10^{d(a)p/2} + (a)_{p/2} \qquad & (pが偶数) \end{cases}$

この漸化式に従って各$(a_i)_{L_i}$を求めれば、あとはそれらを$10^{d(a_i)L_i}$を掛けながら足していけば答えが得られる。

以下、計算量について。

1. $(a_i)_{L_i}$を求める際の再帰の回数は${\mathcal O}(\log L_i)$回
2. $10^k \mod B$は繰り返し二乗法で${\mathcal O}(\log k)$で求まる
3. $d(a_i) = {\mathcal O}(\log a_i)$

したがって、１つの$(a_i)_{L_i}$は${\mathcal O}(\log L_i \cdot \log (d(a_i)L_i)) \subseteq {\mathcal O}(\log L_i \cdot \log \log a_i + \log^2 L_i))$で求まるはず。$a = \max a_i, L = \max L_i$とすると全体の計算量は${\mathcal O}(N(\log L \cdot \log \log a + \log^2 L)))$になる。

計算量をちゃんと考えないまま実装に取り掛かかって、${\mathcal O}(n \log^2 n)$みたいな形になるはずとぼんやり思っていたのだが、だいたい合っていそうで良かった。