結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2021-03-21 19:46:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,076 bytes |
コンパイル時間 | 1,651 ms |
コンパイル使用メモリ | 171,672 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-22 14:42:38 |
合計ジャッジ時間 | 2,798 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#include <bits/stdc++.h>using namespace std;long long motome(long long MOD,long long N){vector<int> two;while(N>0){two.push_back(N%2);N=N/2;}int M=two.size();vector<long long> fibMin1(M),fib(M);fibMin1[0]=0;fib[0]=1;for(int i=1;i<M;i++){fibMin1[i]=fibMin1[i-1]*fibMin1[i-1]%MOD;fibMin1[i]=(fibMin1[i]+fib[i-1]*fib[i-1])%MOD;fib[i]=fibMin1[i-1]*fib[i-1]%MOD;fib[i]=(fib[i]+fib[i-1]*(fib[i-1]+fibMin1[i-1]))%MOD;}long long temp=0,temp2=1;long long r,q;for(int i=0;i<M;i++){if(two[i]){r=temp;q=temp2;temp=q*fib[i]%MOD;temp=(temp+r*fibMin1[i])%MOD;temp2=r*fib[i]%MOD;temp2=(temp2+q*(fib[i]+fibMin1[i]))%MOD;}}return temp;}int main(){long long N;long long MOD=2000000016;cin>>N;if(N==0){cout<<0<<endl;return 0;}long long ans=motome(MOD,N);MOD=1000000007;ans=motome(MOD,ans);cout<<ans<<endl;}