結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー y_y_0916
提出日時 2021-04-26 22:03:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,252 bytes
コンパイル時間 1,715 ms
コンパイル使用メモリ 174,996 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 08:03:01
合計ジャッジ時間 2,360 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

vector<vector<long long>> mat_mul(vector<vector<long long>> a,vector<vector<long long>> b,long long mod){
    long long n,m,l;
    n = a.size();
    m = b.size();
    l = b[0].size();
    vector<long long> v(l);
    vector<vector<long long>> ans_mat(n,v);
    for(int i=0;i<n;i++){
        for(int j=0;j<l;j++){
            for(int k=0;k<m;k++){
                ans_mat[i][j] = (ans_mat[i][j] +  a[i][k] * b[k][j])%mod;
            }
        }
    }
    return ans_mat;
}

vector<vector<long long>> rep_mat_mul(vector<vector<long long>> a,long long n,long long m){
    vector<long long> v(a.size(),0);
    vector<vector<long long>> ans(a.size(), v);
    for(int i=0;i<a.size();i++){
        ans[i][i] = 1;
    }
    while(n>0){
        if(n%2==1){
            ans = mat_mul(ans,a,m);
        }
        a = mat_mul(a,a,m);
        n/=2;
    }

    return ans;
}

int main(){
    long long N,M;
    cin >> N >> M;
    vector<vector<long long>> ans;
    vector<vector<long long>> v = {{1,1},{1,0}};
    ans = rep_mat_mul(v,N-2,M);
    /*
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            cout << ans[i][j] << ' ';
        }
        cout << endl;
    }
    */
   cout << ans[0][0] << endl;
}
0