Potències de permutacions X39049

Donada una $n$, una permutació de $\{0, 1, \ldots n-1\}$ és una seqüència on apareix cadascun dels nombres $0, 1, \ldots n-1$ exactament una vegada. Per exemple, si $n = 3$, les seqüències $(1\ 2\ 0)$, $(2\ 0\ 1)$ i $(0\ 1\ 2)$ són permutacions de $\{0, 1, 2\}$.

Donades dues permutacions $\sigma = (\sigma_{0}, \ldots, \sigma_{n-1})$ i $\tau = (\tau_{0}, \ldots, \tau_{n-1})$ de $\{0$, $1$, $\ldots n-1$ $\}$, el seu producte $\sigma \circ \tau$ es defineix com la permutació $\rho = (\rho_{0}, \ldots, \rho_{n-1})$ tal que $\rho_{i} = \sigma_{\tau_{i}}$. Per exemple, si $n = 3$, $\sigma = (1\ 2\ 0)$ i $\tau = (2\ 0\ 1)$, llavors $\sigma \circ \tau = (0\ 1\ 2)$, perquè:

• $\tau_{0} = 2$ i $\sigma_{2} = 0$,

• $\tau_{1} = 0$ i $\sigma_{0} = 1$, i

• $\tau_{2} = 1$ i $\sigma_{1} = 2$.

Feu un programa que, donada una permutació $\sigma$ i un natural $k$, calculi la potència de $\sigma$ elevada a $k$: $\sigma^k = \overbrace{\sigma \circ \ldots \circ \sigma}^{k)}$. Per conveni, $\sigma^{0} = (0, 1, \ldots, n-1)$.

Entrada

L’entrada inclou diversos casos. Cada cas consisteix en el nombre $n$ ($1 \leq n \leq 10^{4}$), seguit de $n$ nombres entre $1$ i $n$ que descriuen la permutació $\sigma$, seguit del nombre $k$ ($0 \leq k \leq 10^9$).

Sortida

Escriviu la permutació $\sigma^k$.

Observació

La solució esperada per a aquest problema té cost $O(n \cdot \log k)$. Les solucions que tinguin un cost $\Omega(n \cdot k)$ podran aconseguir com a molt $3$ punts sobre $10$.

Podeu afegir unes (poques) línies de comentaris explicant què intenteu fer.

Si us cal, podeu fer servir que el producte de permutacions és associatiu.