yukicoder #492: とても長い数列と文字列(Long Long Sequence and a String）

解法

f(n)を文字列にしたものをS(n)とする。
|S(n)| = 2|S(n)| + (n^2の桁数)
更に|S(4)| = 16 = 2^4
なので
|S(60)|>2^60 が成り立つ。
よってR<|S(60)|であり、K>60の場合は、K=60と見なしてよい。
以下、1<=K<=60とする。
f(n)の各桁の値d(0~9)の出現数を
cnt[n][d]
とする。
これは簡単なDPで求められる。
cnt[n][d] = cnt[n-1][d]*2 + (n^2のなかでのdの出現数)

g(r)をL=1,R=rとしたとき(つまり(0,r])の解を順序対として返す関数とする。
つまり(和,積)を(0, r]について返す。ただし、g(0)は(0, 1)を返す。
この関数が書ければg(R)とg(L-1)によって、
求めたい和は差により、求めたい積は素数10^9+7を法とした除算により、求まる。

g(r)の中身を考えてみよう。
g(0)=(0,1)
であった。

r!=0の場合を考える。
|S(n)|<=rを満たす最大のnをkとする。
(1)|S(k)| = rのとき
ちょうどf(k)の文字化したものを見ればよい。
cnt[k]はすでに求まっているから
和は Σ(x*cnt[k][x])
積は Π(pow(x, cnt[k][x]))
のように求まる。
(2)|S(k)|<rのとき
(1)の計算をしてから、r' = r-|S(k)|とおく。
(2-1) r'<=(k+1)^2の桁数のとき
(k+1)^2の上位r'桁も計算に加える。
(2-2) r'>(k+1)^2のとき
(2-1)の計算をした上で
r'' = r'-( (k+1)^2の桁数 ) として
g(r'')を解いて計算に加える。
2*r''<=rが成り立つからgの再帰の深さはせいぜいlog(r)

べき乗がボトルネックになり、実行時間は

O( (log(R))^2 )

思いつき方

文字列の長さが2倍以上に増えていくことに気づく。

=>f(60)まで