ABC 401-500/ABC450E - Fibonacci String - 競技プログラミング用 知識集積所

---

問題

ABC450E

必要知識

B以下レベルの内容は省略

• 考察問題
• 累積和

考え方

考察問題。
まず、愚直に10^18回文字列を作る必要はなく、長さがRの最大値である10^18を超えたところで止めてよい。
しかしそれでも長さ10^18の文字列を1つ作るだけでメモリも時間も足りない。
この問題は、それをどう解決するか考えることになる。

Sの合成方法は、1つ前の後ろに2つ前をくっつけるというものである。
ということは、「S10の40文字目から50文字目」と言われたとき、S9が50文字以上あるなら実は「S9の40文字目から50文字目」が全く同じものになっている。
逆にS9が40文字ない場合、仮に35文字だったら「S9の40-35=5文字目から50-35=15文字目」と全く同じである。
S9が45文字だったら、「S10の40文字目から45文字目」「S10の46文字目から50文字目」にわけて処理することができる。

つまり、これを繰り返していけば、LとRが10^18に近くても、「S3のX文字目からY文字目」というクエリだけの和にすることができる。
あとは、「クエリを分割しすぎて個数が多くなりすぎる対策」「このクエリを高速に調べる方法」の2つが解決できれば終わり。

前者は、Rが大きい方から順に処理しながら、「こういう範囲のクエリが3個」のように同じクエリをまとめていけばよい。
半端なところから始まるクエリは最大でも1個、半端なところで終わるクエリも最大で1個なので、どれだけ分解しても最大で3種6個のクエリにしかならない。

後者は、S3について、「X文字目までに各文字が何個登場するか」の累積和を事前に作っておくことで、各クエリ引き算1回で求められる。

これでO(|X|+|Y|+ΣlogR)くらいで終わり、定数が重い（アルファベット数で26倍とか）とはいえ間に合う。

解答例

解答例

注意点

別解