結果

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

ソースコード

diff # 

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

typedef vector<vector<long long> > mat;

long long MOD = 1000000007;

long long remainder(long long a, long long mod){
    if(a>=0){
        return a%mod;
    }else{
        return (a+(abs(a)/mod+1)*mod)%mod;
    }
}

mat modmulti(mat A, mat B){
    long long r=A.size();
    long long m=A[0].size();
    long long c=B[0].size();
    vector<long long> O(c,0);
    mat C(r,O);
    long long i,j,k;
    for(i=0; i<r; i++){
        for(j=0; j<c; j++){
            for(k=0; k<m; k++){
                C[i][j]+=A[i][k]*B[k][j];
                C[i][j]=remainder(C[i][j],MOD);
            }
        }
    }
    return C;
}

mat modpow(mat A, long long n) {
    vector<long long> O(A.size(),0);
    mat res(A.size(),O);
    for(long long i=0; i<A.size(); i++){
        res[i][i]=1;
    }
    while (n > 0) {
        if (n & 1) res = modmulti(res,A);
        A = modmulti(A,A);
        n >>= 1;
    }
    return res;
}

int main(){
    //input
    long long N,M;
    cin >> N >> M;
    MOD=M;

    //calc
    vector<long long> O(2,0);
    mat A(2,O);
    A[0][0]=0;
    A[0][1]=1;
    A[1][0]=1;
    A[1][1]=1;
    mat ApowN=modpow(A,N-1);
    vector<long long> verO(1,0);
    mat v(2,verO);
    v[1][0]=1;
    mat ans=modmulti(ApowN,v);

    //output
    cout << ans[0][0] << endl;
    return 0;
}
0