ABC013 D. 阿弥陀
問題
N本の縦棒を横に並べ、上から順にM個の横棒を同じ高さに2本以上入らないようにしてあみだくじを作成する。
i個目の横棒は、a_iとa_i + 1の縦棒を線で結んでいる。
さらに、このあみだくじを縦にD段積んだものを考える。
最終的にi番目から入った場合、何番目の縦棒から出てくるか？をN本すべてについて求めよ。
制約
- 2 <= N <= 10^5
- 0 <= M <= 2 * 10^5
- 1 <= D <= 10^9
解法1
x番目がy番目に動く、という遷移はO(M)で求められる。
1段でこの遷移になるので、2段、4段、8段、、、の場合もダブリングで求められる。
(1つ前を2回行った場合を考えれば良い。)
あとは、Dを2進表現したときビットが立っているところの遷移が行われるので、これをO(N)で求めれば良い。
全体でO(M + N log D)。
解法2
各番号をノードとして、遷移先に辺を張った有向グラフを考える。
この有向グラフは、制約から、自己ループか有向閉路を作る。
各番号は、その番号が所属する有向閉路内をD回遷移することになるので、所属する有向閉路のノード数をXとすると、D mod Xだけ動くのと変わらない。
有向閉路を配列として持っておいて、もし今見ている番号がi番目だとしたら、(i+D) mod X番目にある数字になるのでこれはO(1)で求められる。
したがって、全体でO(M + N)で求められる。
