Potències de permutacions X39049

Donada una n, una permutació de {0, 1, … n−1} és una seqüència on apareix cadascun dels nombres 0, 1, … 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 σ = (σ₀, …, σ_n−1) i τ = (τ₀, …, τ_n−1) de {0, 1, … n−1 }, el seu producte σ ∘ τ es defineix com la permutació ρ = (ρ₀, …, ρ_n−1) tal que ρ_i = σ_τi. Per exemple, si n = 3, σ = (1 2 0) i τ = (2 0 1), llavors σ ∘ τ = (0 1 2), perquè:

• τ₀ = 2 i σ₂ = 0,
• τ₁ = 0 i σ₀ = 1, i
• τ₂ = 1 i σ₁ = 2.

Feu un programa que, donada una permutació σ i un natural k, calculi la potència de σ elevada a k: σ^k = σ ∘ … ∘ σ^k). Per conveni, σ⁰ = (0, 1, …, n−1).

Entrada

L’entrada inclou diversos casos. Cada cas consisteix en el nombre n (1 ≤ n ≤ 10⁴), seguit de n nombres entre 1 i n que descriuen la permutació σ, seguit del nombre k (0 ≤ k ≤ 10⁹).

Sortida

Escriviu la permutació σ^k.

Observació

La solució esperada per a aquest problema té cost O(n · logk). Les solucions que tinguin un cost Ω(n · 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.