結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2017-06-24 00:34:57 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,937 bytes |
コンパイル時間 | 1,064 ms |
コンパイル使用メモリ | 99,916 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-03 04:04:44 |
合計ジャッジ時間 | 2,132 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <algorithm>#include <utility>#include <functional>#include <cstring>#include <queue>#include <stack>#include <math.h>#include <iterator>#include <vector>#include <string>#include <set>#include <math.h>#include <iostream>#include <random>#include<map>#include <iomanip>#include <time.h>#include <stdlib.h>#include <list>#include <typeinfo>#include <list>#include <set>using namespace std;#define eps 0.000000001#define LONG_INF 10000000000000000#define GOLD 1.61803398874989484820458#define MAX_MOD 1000000007#define REP(i,n) for(long long i = 0;i < n;++i)//100000008*2でmodを取るとOK(周期性)vector<long long> calc(vector<long long> a, vector<long long> b,long long modulo) {vector<long long> ans;ans.push_back(((a[0] * b[0]) % modulo + (a[1] * b[2]) % modulo) % modulo);ans.push_back(((a[0] * b[1]) % modulo + (a[1] * b[3]) % modulo) % modulo);ans.push_back(((a[2] * b[0]) % modulo + (a[3] * b[2]) % modulo) % modulo);ans.push_back(((a[2] * b[1]) % modulo + (a[3] * b[3]) % modulo) % modulo);return ans;}int main() {long long n;cin >> n;vector<long long> first_ans;first_ans.push_back(1);first_ans.push_back(0);first_ans.push_back(0);first_ans.push_back(1);vector<long long> multi;multi.push_back(1);multi.push_back(1);multi.push_back(1);multi.push_back(0);while (n != 0) {if (n % 2 == 1) {first_ans = calc(first_ans, multi,2*(MAX_MOD+1));}multi = calc(multi, multi, 2 * (MAX_MOD + 1));n /= 2;}n = first_ans[1];vector<long long> ans;ans.push_back(1);ans.push_back(0);ans.push_back(0);ans.push_back(1);vector<long long> mul;mul.push_back(1);mul.push_back(1);mul.push_back(1);mul.push_back(0);while (n != 0) {if (n % 2 == 1) {ans = calc(ans, mul,MAX_MOD);}mul = calc(mul,mul,MAX_MOD);n /= 2;}cout << ans[1] % MAX_MOD << endl;return 0;}