#969076 (Rust) No.526 フィボナッチ数列の第N項をMで割った余りを求める

• 問題: No.526 フィボナッチ数列の第N項をMで割った余りを求める
• ユーザー: あさくち
• 提出日時: 2024-04-04 20:06:21
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 5,769 bytes
• コンパイル時間: 1,421 ms
• コンパイル使用メモリ: 188,848 KB
• 実行使用メモリ: 6,548 KB
• 最終ジャッジ日時: 2024-04-04 20:06:24
• 合計ジャッジ時間: 2,274 ms
• ジャッジサーバーID （参考情報）: judge13 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,548 KB
testcase_01	AC	1 ms; 6,548 KB
testcase_02	AC	1 ms; 6,548 KB
testcase_03	AC	1 ms; 6,548 KB
testcase_04	AC	1 ms; 6,548 KB
testcase_05	AC	1 ms; 6,548 KB
testcase_06	AC	1 ms; 6,548 KB
testcase_07	AC	1 ms; 6,548 KB
testcase_08	AC	1 ms; 6,548 KB
testcase_09	AC	1 ms; 6,548 KB
testcase_10	AC	1 ms; 6,548 KB
testcase_11	AC	0 ms; 6,548 KB
testcase_12	AC	1 ms; 6,548 KB
testcase_13	AC	1 ms; 6,548 KB
testcase_14	AC	1 ms; 6,548 KB

ソースコード

pub use __cargo_equip::prelude::*;

use asakuchi_input::Input;
use matrix::Matrix;

fn main() {
    let stdin = std::io::stdin();
    let mut input = Input::new(stdin.lock());

    let (n, m): (usize, usize) = input.read();

    let matrix = Matrix::new(vec![vec![1, 1], vec![1, 0]], m);

    let f_n = matrix
        .mat_pow(n - 2)
        .dot(&Matrix::new(vec![vec![1], vec![0]], m));

    println!("{}", f_n.data[0][0]);
}

mod matrix {
    pub use crate::__cargo_equip::prelude::*;

    ///
    /// 行列
    ///
    #[derive(Debug, PartialEq, Eq, Clone)]
    pub struct Matrix {
        pub data: Vec<Vec<usize>>,
        pub row: usize,
        pub column: usize,
        modulus: usize,
    }

    impl Matrix {
        pub fn new(data: Vec<Vec<usize>>, modulus: usize) -> Self {
            let row = data.len();
            let column = data[0].len();

            Self {
                data,
                row,
                column,
                modulus,
            }
        }

        pub fn dot(&self, rhs: &Matrix) -> Self {
            if self.column != rhs.row {
                panic!("self.column != rhs.row");
            }

            let row = self.row;
            let column = rhs.column;

            let mut data = vec![vec![0; column]; row];

            for i in 0..row {
                for j in 0..column {
                    for k in 0..self.column {
                        data[i][j] += self.data[i][k] * rhs.data[k][j];
                        data[i][j] %= self.modulus;
                    }
                }
            }

            Self {
                data,
                row,
                column,
                modulus: self.modulus,
            }
        }

        ///
        /// 行列累乗
        ///
        pub fn mat_pow(&self, x: usize) -> Self {
            if x == 0 {
                // 単位行列
                return Self::identity(self.column, self.modulus);
            }

            if x == 1 {
                return self.clone();
            }

            let mut t = self.mat_pow(x / 2);

            t = t.dot(&t);

            if x % 2 == 1 {
                t = t.dot(&self);
            }

            // 実数を扱う場合は誤差に注意
            // // 正規化
            // let p = t[(0, 0)];
            // let p_not = t[(0, 1)];

            // t *= 1. / (p + p_not);

            t
        }

        ///
        /// 単位行列
        ///
        pub fn identity(size: usize, modulus: usize) -> Self {
            let mut data = Vec::new();

            for i in 0..size {
                let line = (0..size)
                    .map(|j| if i == j { 1 } else { 0 })
                    .collect::<Vec<_>>();
                data.push(line);
            }

            Self {
                data,
                row: size,
                column: size,
                modulus,
            }
        }
    }

    impl std::ops::Rem<usize> for Matrix {
        type Output = Self;

        fn rem(self, modulus: usize) -> Self::Output {
            let mut matrix = self.clone();

            matrix %= modulus;

            matrix
        }
    }

    impl std::ops::RemAssign<usize> for Matrix {
        fn rem_assign(&mut self, modulus: usize) {
            for i in 0..self.row {
                for j in 0..self.column {
                    self.data[i][j] %= modulus;
                }
            }
        }
    }
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `input 0.1.0 (git+https://github.com/asakuchi/procon-library-rs.git?rev=0ff7663d7cdd15f0a73bffebda52373103af0eef#0ff7663d7cdd15f0a73bffebda52373103af0eef)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::asakuchi_input`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod asakuchi_input {use std::io;use std::str;pub trait ParseLine{fn parse_line<R:io::BufRead>(s:&mut Input<R>)->Self;}macro_rules!impl_parse_line{($($t:ty),*)=>{$(impl ParseLine for$t{fn parse_line<R:io::BufRead>(s:&mut Input<R>)->Self{s.token()}})*};}impl_parse_line!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128,isize,f32,f64,String,char);macro_rules!impl_parse_line_tuple{($($t:ident),*)=>{impl<$($t:ParseLine),*>ParseLine for($($t,)*){fn parse_line<R:io::BufRead>(s:&mut Input<R>)->Self{($($t::parse_line(s),)*)}}};}impl_parse_line_tuple!(T0,T1);impl_parse_line_tuple!(T0,T1,T2);impl_parse_line_tuple!(T0,T1,T2,T3);impl_parse_line_tuple!(T0,T1,T2,T3,T4);impl_parse_line_tuple!(T0,T1,T2,T3,T4,T5);impl_parse_line_tuple!(T0,T1,T2,T3,T4,T5,T6);impl_parse_line_tuple!(T0,T1,T2,T3,T4,T5,T6,T7);impl_parse_line_tuple!(T0,T1,T2,T3,T4,T5,T6,T7,T8);impl_parse_line_tuple!(T0,T1,T2,T3,T4,T5,T6,T7,T8,T9);pub struct Input<R>{reader:R,buffer:Vec<String>,}impl<R:io::BufRead>Input<R>{pub fn new(reader:R)->Self{Self{reader,buffer:vec![],}}pub fn token<T:str::FromStr>(&mut self)->T{loop{if let Some(token)=self.buffer.pop(){return token.parse().ok().expect("Failed parse");}let mut input=String::new();self.reader.read_line(&mut input).expect("Failed read");self.buffer=input.split_whitespace().rev().map(String::from).collect();}}pub fn read<T:ParseLine>(&mut self)->T{ParseLine::parse_line(self)}pub fn usize1(&mut self)->usize{self.token::<usize>()-1}pub fn isize1(&mut self)->isize{self.token::<isize>()-1}pub fn chars(&mut self)->Vec<char>{self.token::<String>().chars().collect()}pub fn vec<T:ParseLine>(&mut self,n:usize)->Vec<T>{(0..n).map(|_|ParseLine::parse_line(self)).collect()}}}
    }

    pub(crate) mod macros {
        pub mod asakuchi_input {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod asakuchi_input {}
    }
}