AtCoder Beginner Contest 307 E

https://atcoder.jp/contests/abc307/tasks/abc307_e

状態遷移ですね。最初が0だとして、0という状態と0じゃないという状態を考えればよいです。
行列の演算をGenenicに書いてみましたが、なかなか大変ですね。

// Distinct Adjacent
#![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()
}


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

type Matrix<T> = Vec<Vec<T>>;

fn mat_mul<T>(A: &Matrix<T>, B: &Matrix<T>, D: T) -> Matrix<T>
where
        T: std::ops::Mul + std::ops::Add + std::ops::Rem<Output = T> +
        std::iter::Sum<<T as std::ops::Mul>::Output> + Copy {
    let H = A.len();
    let L = B.len();
    let W = B[0].len();
    let C: Matrix<T> = (0..H).map(|i|
                         (0..W).map(|j|
                          (0..L).map(|k| A[i][k] * B[k][j]).sum::<T>() % D
                         ).collect()
                         ).collect();
    return C
}

fn mat_pow<T>(A: &Matrix<T>, e: usize, D: T) -> Matrix<T>
where
        T: std::ops::Mul + std::ops::Add + std::ops::Rem<Output = T> +
        std::iter::Sum<<T as std::ops::Mul>::Output>
        + std::convert::From<i32> + Copy {
    let delta = |i, j| -> T { T::from(if i == j { 1 } else { 0 }) };
    
    if e == 0 {
        let N = A.len();
        (0..N).map(|i| (0..N).map(|j| delta(i, j)).collect::<Vec<T>>()).
                                                                collect()
    }
    else if e == 1 {
        A.to_vec()
    }
    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 read_input() -> (i64, i64) {
    let v = read_vec();
    let N = v[0];
    let M = v[1];
    (N, M)
}

fn f(N: i64, M: i64, D: i64) -> i64 {
    let A: Matrix<i64> = vec![vec![0, 1], vec![M-1, M-2]];
    let B = mat_pow(&A, N as usize - 1, D);
    M * B[1][0] % D
}

//////////////////// main ////////////////////

fn main() {
    const D: i64 = 998244353;
    let (M, N) = read_input();
    println!("{}", f(M, N, D))
}