AtCoder Beginner Contest 377 E

https://atcoder.jp/contests/abc377/tasks/abc377_e

iからP_iにと辿っていくとループがいくつかできます。そうすると、K=1なら2歩、K=2なら4歩、K=3なら8歩そのループを進みます。
べき乗の計算はi128を使うと簡単ですね。

// Permute K times 2
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn pow_mod(b: i128, e: i128, d: i128) -> i128 {
    if e == 1 {
        b
    }
    else if e % 2 == 1 {
        b * pow_mod(b, e - 1, d) % d
    }
    else {
        let p = pow_mod(b, e / 2, d);
        p * p % d
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<usize>) {
    let v: Vec<usize> = read_vec();
    let K = v[1];
    let P1: Vec<usize> = read_vec();
    let P: Vec<usize> = P1.into_iter().map(|i| i-1).collect();
    (K, P)
}

type Loop = Vec<usize>;

fn find_loop(i: usize, P: &Vec<usize>) -> Loop {
    let mut k = i;
    let mut l: Loop = vec![i];
    k = P[k];
    loop {
        if k == i {
            break
        }
        l.push(k);
        k = P[k]
    }
    l
}

fn F(K: usize, P: Vec<usize>) {
    let N = P.len();
    let mut loops: Vec<Loop> = vec![];
    let mut loop_ids: Vec<usize> = vec![N; N];
    for i in 0..N {
        if loop_ids[i] != N {
            continue
        }
        let l = find_loop(i, &P);
        for j in l.iter() {
            loop_ids[*j] = loops.len()
        }
        loops.push(l);
    }
    
    let mut v: Vec<usize> = vec![0; N];
    for l in loops.into_iter() {
        let L = l.len();
        let R = pow_mod(2, K as i128, L as i128) as usize;
        for i in 0..L {
            v[l[i]] = l[(i+R)%L]
        }
    }
    
    println!("{}", v.into_iter().map(|i| (i+1).to_string()).
                                    collect::<Vec<_>>().join(" "))
}

fn main() {
    let (K, P) = read_input();
    F(K, P)
}