アルゴリズムと数学 055

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_au

行列が変わるだけですね。

// Recurrence Formula 1
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: i64 = 1000000007;


//////////////////// 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()
}


//////////////////// Matrix ////////////////////

type Matrix = Vec<Vec<i64>>;

fn mat_mul(A: &Matrix, B: &Matrix, d: i64) -> Matrix {
    let L = A.len();
    let M = B.len();
    let N = B[0].len();
    (0..L).map(|i| (0..N).
            map(|j| (0..M).map(|k| (A[i][k] * B[k][j]) % d).sum::<i64>() % d).
                                                    collect::<Vec<i64>>()).
                                                    collect::<Matrix>()
}

fn mat_pow(A: &Matrix, e: u64, d: i64) -> Matrix {
    if e == 1 {
        A.clone()
    }
    else if e % 2 == 0 {
        let B = mat_pow(&A, e/2, d);
        mat_mul(&B, &B, d)
    }
    else {
        mat_mul(&A, &mat_pow(&A, e-1, d), d)
    }
}


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


fn f(N: u64) -> i64 {
    let A = vec![vec![0, 1], vec![1, 2]];
    let P = mat_pow(&A, N-2, D);
    (P[1][0] + P[1][1]) % D
}

fn main() {
    let N = read();
    println!("{}", f(N))
}