AtCoder Beginner Contest 013 D 阿弥陀
D - 阿弥陀
時間制限 : 4sec / メモリ制限 : 256MB
問題文
古くより伝わる日本の伝統的なくじ引き、あみだくじをご存知だろうか？
あみだくじを行うときは、まず N 本の平行な縦線を引く。次に、M 本の横線をその中に引いていく。それぞれの横線は隣り合う 2 本の縦線を結ぶように引かなければならず、2 本以上の横線がまったく同じ高さにあってはいけない。ここでは、上から i (1 ≦ i ≦ M) 番目にある横線が、左から Ai (1 ≦ Ai<N) 番目の縦線と Ai+1 番目の縦線を結んでいるとしよう。
N=5, M=7, A={1,4,3,4,2,3,1} の場合のあみだくじを以下に示す。くじを引くときは、縦線を 1 本選び、その上端から線を下っていく。途中で横線に遭遇したときには必ず曲がらなければならず、また縦線を上向きに辿ってはいけない。たとえばこのあみだくじで左から 4 番目の縦線から始めてくじを引くと、左から 3 番目の縦線に辿り着く。
さて、ここまでは普通のあみだくじであるが、何かにつけビッグデータという言葉が騒がれる昨今である。あみだくじがこれから先生きのこるためには、あみだくじもビッグになってビッグデータに対抗していかなければならない。
そこで、あみだくじを縦に D 個つなげることで巨大なあみだくじを作ることを考えよう。たとえば、先ほど例に挙げたあみだくじを 2 個つなげてみると以下のようになる。この場合、左から 4 番目の縦線から始めてくじを引くと、辿り着く場所は左から 5 番目の縦線になる。
こうして作った巨大あみだくじだが、あみだくじ本来の目的を果たせなければビッグになった意味もない。つまり、この巨大なあみだくじを使ってくじを引いた結果がどうなるかを効率よく計算できなければ、せっかく作った巨大あみだくじもただの落書きである。
そこで、1 ≦ k ≦ N を満たすすべての整数 k に対し、巨大あみだくじの左から k 番目の縦線を選んで線を辿っていったとき、最終的に下端で左から何番目の縦線に行き着くかを計算するプログラムを書いて欲しい。
note
まず１個のあみだくじで最初i番目からスタートでどこにたどり着くかは、横線がある度に、位置をswapしてあげれば良いのでO(M)でわかる。次に、このあみだの個数Gが109とかなり大きいので、それぞれのあみだのスタート地点からどこにいくかを工夫しないとO(NG + M)になってしまい解けない。これをとくためにダブリングを用いる。ダブリングはある数の累乗を求めるときなどにも使われる。Ti(n)をi番目からスタートしてn個のあみだをつなげた際に、何番目にたどり着くかを返す関数とするとTi(n2) = Ti(Ti(n)) となることを利用する。これによってO(Nlog(G) + M)で求めることができる。
