yukicoder No.1013 ○マス進む
問題
N個の要素からなる順列Pを無限につなげた数列Tを考える。
T上のi番目にいる場合、1回の移動では、「i+T_i番目」に移動する。
K回後に何番目にいるか？をi=1,...,Nについてそれぞれ求めよ。
制約
- 1 <= N <= 10^5
- 1 <= K <= 10^9
- Pは{1,2,...,N}を並び替えた順列
解法
K回後の移動先を高速に求めるためには、ダブリングが有効。
xの位置にいるとき、1回後、2回後、4回後、8回後、、、の移動量を求めておく。
これは、
db[i][j] := 位置がj=x%Nに2^i回移動した場合、いくら移動するか？
を考えると、
db[0][j] = P[j]
として、
// jから2^(i+1)回移動したときの移動量 ＝ jから2^i回移動したときの移動量 ＋ jから2^i移動したあとの位置から2^i回移動したときの移動量 db[i+1][j] = db[i][j] + db[i][(db[i][j]+j)%N]
で更新できる。
そして、j番目のK回の移動先は、jからスタートして、Kのビットが立っているiについてdb[i][pos%N]を加算し続けていけば求められる。
