結果
問題 | No.526 フィボナッチ数列の第N項をMで割った余りを求める |
ユーザー | moricup |
提出日時 | 2020-09-17 23:40:11 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 1 ms
6,944 KB |
ソースコード
#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; }