結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー Ryosuke Kawashima
提出日時 2026-05-22 00:37:31
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,212 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,231 ms
コンパイル使用メモリ 189,164 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-22 00:37:54
合計ジャッジ時間 13,752 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;
// yukicoder No.526
// Q. Remainder of Nth Fibonacci number modulo M
// A. Matrix exponentiation: 行列累積乗
fn main() {
    input!{n: usize, m: usize}
    let base_matrix: [[usize; 2]; 2] = [[1, 1], [1, 0]];
    let result_matrix: [[usize; 2]; 2] = matrix_pow(base_matrix, n, m);
    println!("{}", result_matrix[1][1] % m);
}

fn matrix_pow(matrix: [[usize; 2]; 2], mut exponent: usize, modulus: usize) -> [[usize; 2]; 2] {
    let mut result: [[usize; 2]; 2] = [[1, 0], [0, 1]];
    let mut base: [[usize; 2]; 2] = matrix;
    while exponent > 0 {
        if exponent % 2 == 1 {
            result = matrix_mult(result, base, modulus);
        }
        base = matrix_mult(base, base, modulus);
        exponent /= 2;
    }
    return result;
}

fn matrix_mult(mat1: [[usize; 2]; 2], mat2: [[usize; 2]; 2], modulus: usize) -> [[usize; 2]; 2] {
    let mut result: [[usize; 2]; 2] = [[0; 2]; 2];
    for i in 0..2 {
        for j in 0..2 {
            for k in 0..2 {
                let prod = (mat1[i][k] as u128) * (mat2[k][j] as u128);
                result[i][j] = ((result[i][j] as u128 + prod) % (modulus as u128)) as usize;
            }
        }
    }
    return result;
}
0