結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー macaroni5708
提出日時 2026-02-05 09:27:39
言語 Rust
(1.93.0 + proconio + num + itertools)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,654 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,944 ms
コンパイル使用メモリ 211,592 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-02-05 09:27:57
合計ジャッジ時間 6,522 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `std::cmp::Reverse`
  --> src/main.rs:10:5
   |
10 | use std::cmp::Reverse;
   |     ^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

warning: variable `MOD` should have a snake case name
  --> src/main.rs:57:53
   |
57 | fn matrix_mul(a: &[[u64; 2]; 2], b: &[[u64; 2]; 2], MOD: u64) -> [[u64; 2]; 2] {
   |                                                     ^^^
   |
   = note: `#[warn(non_snake_case)]` (part of `#[warn(nonstandard_style)]`) on by default
help: rename the identifier or convert it to a snake case raw identifier
   |
57 - fn matrix_mul(a: &[[u64; 2]; 2], b: &[[u64; 2]; 2], MOD: u64) -> [[u64; 2]; 2] {
57 + fn matrix_mul(a: &[[u64; 2]; 2], b: &[[u64; 2]; 2], r#mod: u64) -> [[u64; 2]; 2] {
   |

ソースコード

diff #
raw source code 

#[allow(unused_imports)]
//use ac_library::{ModInt998244353 as Mint, *};
#[allow(unused_imports)]
use itertools::{Itertools, iproduct};
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Usize1},
};
use std::cmp::Reverse;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
    };
}

#[fastout]
fn main() {
    input! {n:u64,m:u64}
    println!("{}", fibonacci(n - 1, m) % m);
}

/// 行列累乗による高速フィボナッチ数計算 (0-indexed)
/// fib(0) = 0, fib(1) = 1
fn fibonacci(n: u64, m: u64) -> u64 {
    if n == 0 {
        return 0;
    }

    // 基本行列 [[1, 1], [1, 0]]
    let mut a = [[1, 1], [1, 0]];
    matrix_pow(&mut a, n - 1, m);

    a[0][0] // fib(n)
}

/// 2x2行列の累乗（繰り返し二乗法）
fn matrix_pow(mat: &mut [[u64; 2]; 2], mut exp: u64, m: u64) {
    let mut res = [[1, 0], [0, 1]]; // 単位行列

    while exp > 0 {
        if exp % 2 == 1 {
            res = matrix_mul(&res, mat, m);
        }
        *mat = matrix_mul(mat, mat, m);
        exp /= 2;
    }

    *mat = res;
}

/// 2x2行列の積
fn matrix_mul(a: &[[u64; 2]; 2], b: &[[u64; 2]; 2], MOD: u64) -> [[u64; 2]; 2] {
    [
        [
            (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD,
            (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD,
        ],
        [
            (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD,
            (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD,
        ],
    ]
}
0