Powers of permutations

Go to the Jutge statement of the problem

Given a natural number n, a permutation of \{0, 1,\dots,n−1\} is a sequence where each of the numbers 0, 1, …, n−1 occurs exactly once. For example, if n = 3, the sequences (1 2 0), (2 0 1) and (0 1 2) are permutations of \{0, 1, 2\}.

Given two permutations \sigma = (\sigma_0, \dots, \sigma_{n−1}) and \tau = (\tau_0, \dots, \tau_{n−1}) of \{0, 1, \dots,n−1\}, their product \sigma\circ\tau is defined as the permutation \rho = (\rho_0, \dots, \rho_{n−1}) such that \rho_i = \sigma_{\tau_i}. For example, if n = 3, \sigma = (1 2 0) and \tau = (2 0 1), then \sigma\circ\tau = (0 1 2), since:

\tau_0 = 2 and \sigma_2 = 0,
\tau_1 = 0 and \sigma_0 = 1, and
\tau_2 = 1 and \sigma_1 = 2.

Make a program that, given a permutation \sigma and a natural k, computes the power of \sigma raised to k, that is \sigma^k = \underbrace{\sigma \circ\cdots\circ\sigma}_k. By convention, \sigma^0 = (0, 1, …, n−1).

Input: The input includes several cases. Each case consists in the number n (1 \leq n \leq 10^4), followed by n numbers between 1 and n that describe the permutation \sigma, followed by the number k (0 \leq k \leq 10^9).

Output: Write the permutation \sigma^k.

If needed, you can use that the product of permutations is associative.

The expected solution to this problem has cost O(n \log k).

Hint

Nothing really changes from the previous exercises. Just the meaning of the product.

A possible C++ code to start the problem

// Powers of permutations
#include<iostream>
#include<vector>

using namespace std;

typedef vector<int> Permutation;

int n;//the length of the permutations

Permutation operator*(const Permutation& s, const Permutation& t){
    Permutation c(n);
    // compute the product of two permutations
    return c; 
}

Permutation power(const Permutation& s, int k){
    Permutation out(n);
    // compute the power, as in the previous exercises. 
    // Is the code here affected by the fact that * has a different meaning than the * between integers 
    // or matrices?
}


int main(){
    while(cin >> n){
        Permutation perm(n);
        for(int i = 0; i < n; ++i)
            cin  >> perm[i];
        int k;
        cin >> k;
        Permutation pow = power(perm,k);
        // write to cout the permutation
    }
}

A possible solution

// Powers of permutations
#include<iostream>
#include<vector>

using namespace std;

typedef vector<int> Permutation;

int n;//the length of the permutations

Permutation operator*(const Permutation& s, const Permutation& t){
    Permutation c(n);
    for (int i = 0; i < s.size(); ++i)
        c[i] = s[t[i]];
    return c; 
}

Permutation power(const Permutation& s, int k){
    Permutation out(n);
    if (k==0){
        for (int i = 0; i < n; ++i)
            out[i]=i;
        return out;
    }
    out = power(s, k/2);
    return (k%2==0) ? out*out : s*out*out;
}


int main(){
    while(cin >> n){
        Permutation perm(n);
        for(int i = 0; i < n; ++i)
            cin  >> perm[i];
        int k;
        cin >> k;
        Permutation pow = power(perm,k);
        for(int i = 0; i < n; ++i)
            cout << ((i==0) ? "" : " ") << pow[i];
        cout << endl;
    }
}

Other Links