アルゴリズムと数学 053

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

を使ってもよいですが、行列などで割り算ができないこともあります。そういう時は繰り返し2乗法のように和を取る方法が使えます。

などと再帰的に求めればよいです。

// Sum of 4^N
#![allow(non_snake_case)]


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

const D: u64 = 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()
}


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

// n, e, d -> ((1+n+...+n^(e-1)) % d, n^e % d)
fn sum_pow(n: u64, e: u64, d: u64) -> (u64, u64) {
    if e == 1 {
        (1, n)
    }
    else if e % 2 == 0 {
        let (s, p) = sum_pow(n, e/2, d);
        (s * (1 + p) % d, p * p % d)
    }
    else {
        let (s, p) = sum_pow(n, e-1, d);
        ((1 + n * s) % d, p * n % d)
    }
}

fn f(N: u64) -> u64 {
    let (s, p) = sum_pow(4, N+1, D);
    s
}

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