結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー Yohei TamuraYohei Tamura
提出日時 2020-09-19 18:13:39
言語 Rust
(1.77.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,977 bytes
コンパイル時間 2,323 ms
コンパイル使用メモリ 153,324 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-05 22:51:01
合計ジャッジ時間 3,301 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports)]
#![allow(unused_macros)]
use std::cmp::{max, min};
use std::collections::*;
use std::i64;
use std::io::{stdin, Read};
use std::usize;

trait ChMinMax {
    fn chmin(&mut self, other: Self);
    fn chmax(&mut self, other: Self);
}
impl<T> ChMinMax for T
where
    T: PartialOrd,
{
    fn chmin(&mut self, other: Self) {
        if *self > other {
            *self = other
        }
    }
    fn chmax(&mut self, other: Self) {
        if *self < other {
            *self = other
        }
    }
}

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, $var:ident $($r:tt)*) => {
        let $var = parse_val!($it, usize);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: tt),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, u1) => {
        $it.next().unwrap().parse::<usize>().unwrap() -1
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn matmulmod(a: &[Vec<usize>], b: &[Vec<usize>], m: usize) -> Vec<Vec<usize>> {
    assert_eq!(a[0].len(), b.len());
    (0..a.len())
        .map(|i| {
            (0..b[0].len())
                .map(|k| {
                    (0..b.len())
                        .map(|j| (a[i][j] * b[j][k]) % m)
                        .fold(0, |x, y| (x + y) % m)
                })
                .collect()
        })
        .collect()
}

fn idmat(n: usize) -> Vec<Vec<usize>> {
    let mut ret = vec![vec![0; n]; n];
    for i in 0..n {
        ret[i][i] = 1;
    }
    ret
}

fn matpowmod(a: &Vec<Vec<usize>>, mut p: usize, m: usize) -> Vec<Vec<usize>> {
    let n = a.len();
    let mut ret = idmat(n);
    let mut cur = a.clone();
    while p > 0 {
        if p & 1 == 1 {
            ret = matmulmod(&ret, &cur, m);
        }
        cur = matmulmod(&cur, &cur, m);
        p >>= 1;
    }
    ret
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, n: usize, m: usize);
    if n == 1 {
        println!("{}", 0);
    } else if n == 2 {
        println!("{}", 1);
    } else {
        let a = vec![vec![1, 1], vec![1, 0]];
        let b = matpowmod(&a, n - 2, m);
        let v = vec![vec![1], vec![0]];
        let w = matmulmod(&b, &v, m);
        println!("{}", w[0][0]);
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}
0