二分木と周期性 - Githubissues

tipstar0125 / atcoder

atcoder

6 stars 0 forks source link

Open tipstar0125 opened 7 months ago

tipstar0125 commented 7 months ago

tipstar0125 commented 7 months ago

S(0)のどこから派生するか考える⇒tが大きいとき(t > 10^18)明らかに0文字目(0-indexed)からの派生。小さい時は、kを2^tで割った値番目。1文字当たり、2^tに倍増するので、派生毎に考える場合は、kはk%=2^tとする。
二分木で考えると、Aで始まると、左の子がB、右の子がCとなり、それぞれ+1、+2となる。最初の値と、左に行く回数と右に行く回数のmod3で答えを求められる。

tipstar0125 commented 7 months ago

右の子にいくときは、ビットシフトして、0を足し（実際はシフトのみ）、左の子に行くときはビットシフトして1を足す。