2019年4月8日月曜日

ARC 020 C - A mod B Problem

ARC 020 C - A mod B Problem

整数aaの10進表示をpp個並べてできた数を(a)p(a)_pと書くことにし、aaの10進表示の長さをd(a)d(a)とする。(a)pmod  B(a)_p \mod Bは繰り返し二乗法の要領で計算できる1:
(a)p={0(p=0)(a)p110d(a)+a(p)(a)p/210d(a)p/2+(a)p/2(p) (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}

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

以下、計算量について。

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

したがって、1つの(ai)Li(a_i)_{L_i}O(logLilog(d(ai)Li))O(logLiloglogai+log2Li)){\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=maxai,L=maxLia = \max a_i, L = \max L_iとすると全体の計算量はO(N(logLlogloga+log2L))){\mathcal O}(N(\log L \cdot \log \log a + \log^2 L)))になる。

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


  1. 一般にダブリングと呼ぶらしい。https://www.slideshare.net/satanic2/ss-72500089 がわかりやすかった。 ↩︎