アルゴリズムと数学 054

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

$b_n \equiv a_{n+1}$ とすると、

$\begin{cases} a_{n+1} = b_n \\ b_{n+1} = a_n + b_n \end{cases}$

と書けます。これを行列表示にすると、

$A \equiv \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$

とおくと、

$\begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = A \begin{pmatrix} a_n \\ b_n \end{pmatrix}$

だから、

$\begin{pmatrix} a_n \\ b_n \end{pmatrix} = A^{n-1} \begin{pmatrix} 1 \\ 1 \end{pmatrix}$

となります。あるいは、

$\begin{pmatrix} a_n \\ b_n \end{pmatrix} = A^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}$

と書けます。

// Fibonacci Hard (mod 1000000000)
#![allow(non_snake_case)]


//////////////////// Constants ////////////////////

const D: i64 = 1000000000;


//////////////////// 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, 1]];
    let P = mat_pow(&A, N, D);
    P[0][1]
}

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