ABC241 E - Putting Candies (500)
コンテスト中の解法
ある皿$ iにいるときに次に操作する皿は$ i + A_i \pmod n
一度訪れた皿を記憶しておいて、一度訪れた皿に再訪する所まで移動を繰り返す
これでどこからループが始まるか、ループの周期が分かる
ループが始まる場所まで移動した後、残りの回数をループの周期で割る
ループが始まる以前の所までで操作が終わる場合はそれを出力する
残りの回数を移動した飴の個数が答え
個数はmodを取らないのに注意
ダブリングの解法
ダブリングで解く
それぞれの$ N個の状態から次にどの皿の状態に移動するかと飴が何個増えるかを記録しておく
一緒に持つと面倒なので別の配列にあると良い
$ K \le 10^{12}なので一つ手前の情報を使って$ 2^1, 2^2, \ldots, 2^{38}, 2^{39}回後の移動後の状態も求めておく
これらの情報を使って$ k回後の状態を出力