アルゴリズムと数学 056

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

とおけば、

なので、行列表示にすると、

3×3の行列になるだけで、あとは同じです。

// Recurrence Formula 2
#![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, 0], vec![0, 0, 1], vec![1, 1, 1]];
    let P = mat_pow(&A, N-1, D);
    (P[0][0] + P[0][1] + P[0][2] * 2) % D
}

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