結果
問題 |
No.720 行列のできるフィボナッチ数列道場 (2)
|
ユーザー |
|
提出日時 | 2020-03-27 05:01:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,058 bytes |
コンパイル時間 | 475 ms |
コンパイル使用メモリ | 64,452 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-02 08:05:31 |
合計ジャッジ時間 | 1,382 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
コンパイルメッセージ
main.cpp:31:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type] 31 | main() | ^~~~
ソースコード
#include<iostream> #include<array> using namespace std; const long mod=1e9+7; template<int N> array<array<long,N>,N>pw(array<array<long,N>,N>A,long K) { array<array<long,N>,N>ret; for(int i=0;i<N;i++)for(int j=0;j<N;j++)ret[i][j]=i==j?1:0; while(K) { if(K&1) { array<array<long,N>,N>tmp; for(int i=0;i<N;i++)for(int j=0;j<N;j++)tmp[i][j]=ret[i][j],ret[i][j]=0; for(int i=0;i<N;i++)for(int j=0;j<N;j++) { for(int k=0;k<N;k++)(ret[i][j]+=tmp[i][k]*A[k][j])%=mod; } } K>>=1; array<array<long,N>,N>tmp; for(int i=0;i<N;i++)for(int j=0;j<N;j++)tmp[i][j]=A[i][j],A[i][j]=0; for(int i=0;i<N;i++)for(int j=0;j<N;j++) { for(int k=0;k<N;k++)(A[i][j]+=tmp[i][k]*tmp[k][j])%=mod; } } return ret; } main() { long N,M; cin>>N>>M; array<array<long,2>,2>D; D[0][0]=1; D[0][1]=1; D[1][0]=1; D[1][1]=0; D=pw<2>(D,M); array<array<long,3>,3>F; F[0][0]=D[0][0]; F[0][1]=D[0][1]; F[1][0]=D[1][0]; F[1][1]=D[1][1]; F[0][2]=F[1][2]=0; F[2][0]=D[0][0]; F[2][1]=D[0][1]; F[2][2]=1; F=pw<3>(F,N); cout<<F[2][1]<<endl; }