[問題案] {0,1,...,n-1} 上の関数の累乗

[SSRS-cp]

問題ID: ? 問題名: ?

想定アルゴリズム: 周期性を利用してまとめる

問題概要

長さ N の整数列 a_0, a_1, ..., a_{N-1} が与えられる。0≦a_i<N である。また、整数 X が与えられる。 b_i=a_a_...a_i (a が X 個) とする。各 i について b_i を求めよ。

入力

N
a_0 a_1 ... a_{N-1}
X

出力

b_0 b_1 ... b_{N-1}

制約

1≦N≦5×10^5 0≦a_i<N 0≦X≦10^18

メモ

もっといい感じの問題文があるかもしれないです

[maspypy]

functional graph という言葉を問題名に入れるとわかりやすそう？X はクエリにしてもよいかと。

[SSRS-cp]

クエリ

「i, X が与えられて、i に x→a_x を X 回やった後の値を答える」ということですか？

[maspypy]

はい

[SSRS-cp]

それは少し難しくなりませんか (Level Ancestor が部分問題なので)

[maspypy]

ああ線形時間でやりたいってことですか。把握。

[SSRS-cp]

はい ダブリングで Θ(NlogX) は簡単ですが、O(N) の実装は割とややこしいので問題を立ててもよいかなと思いました。