結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー 1831三﨑颯
提出日時 2020-11-20 16:30:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,142 bytes
コンパイル時間 1,090 ms
コンパイル使用メモリ 80,784 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-23 12:11:10
合計ジャッジ時間 1,894 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<long long> dp;

void matsquare(vector<vector<long long>> &fibmat) {
    vector<vector<long long>> ret(2, vector<long long>(2));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                ret[i][j] += fibmat[i][k] * fibmat[k][j] % M;
                ret[i][j] %= M;
            }
        }
    }
    fibmat = ret;
}

void matmul(vector<vector<long long>> &fibmat) {
    vector<long long> n(2);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            n[i] += fibmat[i][j] * dp[j] % M;
            n[i] %= M;
        }
    }
    dp = n;
}

void matpow(int n) {
    vector<vector<long long>> fibmat(2, vector<long long>(2));
    fibmat[0][0] = 1; fibmat[0][1] = 1; fibmat[1][0] = 1;
    while (n > 0) {
        if (n & 1) {
            matmul(fibmat);
        }
        n /= 2;
        matsquare(fibmat);
    }
}

int main(void){
    cin >> N >> M;
    dp.resize(2);
    dp[0] = 0; dp[1] = 1;
    
    matpow(N-1);
    
    cout << dp[0] << endl;
}
0