Good Bye 2015 D - New Year and Ancient Prophecy
TLで少しだけ話題になっていたのと、文字列アルゴリズムはこんなところにも使えて便利だから勉強しようという面で
としよう。
そうすると、
であることは、明らかであろう。
でこの遷移そのものは累積和DPをつかえば、全体ででできることもわかる。
さて問題は多倍長整数の大小比較である。ここがでできないと
と非常に大きいのでTLEする可能性が高い。
ここで使えるのがZ - Algorithmである。
というのもZ - Algorithmは先頭何文字が同じかを判定するアルゴリズムであるが、これはまさしく多倍長の大小判定そのものである(同じところの次の桁の大小比較をすればいいだけなので)
Z - Algorithmを使った大小比較の計算量は、前計算 で 判定は
でできる。
以上でこの問題を解くことができました。
ちなみにRolling Hashを使うとでできるが、Rolling Hashの定数倍はmodをとる関係でそこそこ重いので通る保証はあまりない…
