No.493

$f(i)$ の文字列化した長さを $s(i)$, $i$ を文字列化した長さを $\langle i \rangle$ とする. このとき,

$$s(i) = 2s(i-1) + \langle i^2 \rangle$$

となる. これを計算してみるとわかるが, $i = 60$ で $s(i) \gt 10^{18}$ となるので, $K \geq 60$ の場合は $K = 60$ としていい.

続いて, $f(i)$ を文字列化して各桁の和を求めた数を $t(i)$, $i$ を文字列化して各桁の和を求めた数を $[i]$ とする. このとき,

$$t(i) = 2t(i-1) + [i^2]$$

となる.

ここから, 区間 $[l, r)$ が指定されたときの和を考える. $l, r$ は 0-index で与えられるとする. 当然ながら $r \geq s(K)$ のときは -1 である.

$K$ が指定されたときの区間 $[l, r)$ の和を $x(K, l, r)$ とする.

$l = 0, r = s(K)$ のときは $t(K)$ を返す.

$l \lt s(K)$ のときは以下のようになる.

• $r \leq s(K)$ のときは $x(K-1, l, r)$.
• $r \leq s(K-1) + \langle K^2 \rangle$ のときは $x(K-1, l, s(K-1))$ に $K^2$ を数値化したものから前半 $r-s(K-1)$ 文字を取り出して和を計算したものを足す.
• $r \gt s(K-1) + \langle K^2 \rangle$ のときは $x(K-1, l, s(K-1)) + [K^2] + x(K-1, 0, r-s(K-1)-\langle K^2 \rangle)$.

$l \lt s(K-1) + \langle K^2 \rangle$ のときは以下のようになる.

• $r \leq s(K-1) + \langle K^2 \rangle$ のときは $K^2$ を数値化したものから区間 $[l-s(K-1), r-s(K-1))$ の文字を取り出して和を計算したものである.
• $r \gt s(K-1) + \langle K^2 \rangle$ のときは $x(K-1, 0, r-s(K-1)-\langle K^2 \rangle)$ に $K^2$ を数値化したものから前半 $l-s(K-1)$ 文字を取り除いて和を計算したものを足す.

$l \geq s(K-1) + \langle K^2 \rangle$ のときは $x(K-1, l-s(K-1)-\langle K^2 \rangle, r-s(K-1)-\langle K^2 \rangle)$ である.