(cache)ACPC VC 2019/12/04 DIV1

実装力、破滅…

ダブリングをします　終わり　なんでバグるんですか？（４敗）

aからbへの移動回数を求めるときは以下のようにする

十分大きなkから考えて、2^k回移動してもbにたどり着かないなら移動する
最後にちょうど1回移動する

あるkで移動しなかった場合、移動に必要な回数は $2^{k}$ 回以下である
$\sum_{i = 0}^{k - 1} 2^{i} = 2^{k} - 1$ であるからちょうど $2^{k}$ 回必要な時はこれでよい
そうでないならある $l (l < k)$ で移動しないはずで、帰納法が回る

dbl[k][a]<=bでやると右端で大変なことになるので気をつけよう！

自明なケースを除くと分割は2つ　証明：前それで解いた

文字列の周期という概念がある
周期を二つ持つとき、そのgcdもまた周期になる

今日つぶあんくんに教えてもらった簡潔な証明：
Sを元の文字列を前後に無限個付け足した文字列とする
S[a] = S[a+x]=S[a+x+y]=S[a+kx+ly]
なので、拡張ユークリッドの互除法を考えるとgcd(x,y)のところは全て等しい

gcd(n,n-1) = 1 であることから、w[0:n) とw[0:n-1) が共に文字列の繰り返しで表される場合、全ての文字が同じ文字列になる　そのケースは自明

あとは文字列の長さを決め打ってLCPをすればよい　今回はprefixとsuffixだけなのでZ-algoでできる
まあめんどくさいからSuffixArray+LCPを貼った

ヘラヘラしながら二重ループを書いたらO(N^2) になっていた（なんで？
調和級数にするやつは前計算するのが楽

あまりにも有名
www.nicovideo.jp

beet's soil