ABC242D ABC Transform - geam1113’s diary

解説AC

テキストとyoutubeの解説の自分用まとめです。特に新しいことはありません。公式を見た方が詳細です。

各文字が2つの文字になることを順に図示すると、二分木の構成になります。

よって、この問題は、

$S^{(0)}_0,\ S^{(0)}_1,\ \cdots S^{(0)}_{N-1}$ を根とする二分木における、深さ $t$ で $k$ 番目の文字を求めよ

という問題と見ることができます。

$mod\ 3$ における0,1,2をA,B,Cに対応させます。
Aの左子ノードがB、右子ノードがCであるとします。
左子ノードに進むことは、 $mod\ 3$ において+1すること、右子ノードに降りることは+2することと同じです。B,Cにおいても同様に考えることができます。

よって、親の文字がわかれば子の文字を求めることができます。

以降、+xするという表現は $mod\ 3$ 上での操作を指します。

深さ $t$ において、 $k$ 番目である場合、その子は、深さ $t+1$ において、左子ノードが $2k$ 番目、右子ノードが $2k+1$ となります。

以下が理由です。
深さ $t$ において $k$ 番目である場合、自分より前には $0,...,k-1$ までの $k$ 個のノードが存在する。
深さ $t+1$ には、それらの子ノードが2個ずつ存在し、その数は $2k$ 個となる。それらの番号は、 $0,...,2k-1$ となるから。

これより、

が言えます。
また、

も言えます。

解説にならって、 $S^{(t)}$ の $k$ 番目の文字を求める関数を $f(t,k)$ とおきます。

以下のように再帰的に求められます。

$f(t-1,\lfloor \frac{k}{2} \rfloor )$ を求め、 $k$ が偶数なら+1、奇数なら+2します。
$t$ が十分小さい場合、再帰の過程で $t=0$ となります。この時、 $f(0,k')$ を $S^{(0)}_{k'}$ として返せばよいです。

深さが1増えると子の数は2倍になります。
深さ $d$ から、60回深いところに進むと、 $0,...,2_{60}-1$ 番目の文字は全て $S^{(d)}_0$ の子孫であることがわかります。

$k$ の最大値は $10^{18} \lt 2^{60}-1$ であることから、 $t$ から60回ほど親を遡ったところを $t'$ とすれば、深さ $t$ の $k$ 番目の文字は全て $S^{(t')_0}$ の子孫となります。

ある深さ $d$ における $S^{(d)}_0$ は、全て $S^{(0)}_0$ の左子ノードを $d$ 回進んだ文字であるので、 $S^{(0)}_0+d$ することで求められます。

以上より、再帰において $k$ を1/2していくと、高々60回ほどで、 $k=0$ となります。このとき、 $f(t',0)$ を $S^{(0)}_0+t'$ として返すようにすればよいです。
提出コード(公式とほぼ同じ)