結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2017-06-23 22:38:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,928 bytes |
コンパイル時間 | 1,637 ms |
コンパイル使用メモリ | 168,152 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-02 14:52:50 |
合計ジャッジ時間 | 2,838 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }template<int MOD>struct ModInt {static const int Mod = MOD;unsigned x;ModInt() : x(0) { }ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }int get() const { return (int)x; }ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }ModInt operator+(ModInt that) const { return ModInt(*this) += that; }ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }};typedef ModInt<1000000007> mint;unsigned long long modmult(unsigned long long x, unsigned long long y, unsigned long long MOD) {x %= MOD, y %= MOD;unsigned long long a = x, r = 0;while (y) {if (y & 1)if ((r += a) >= MOD) r -= MOD;if ((a += a) >= MOD) a -= MOD;y >>= 1;}return r;}unsigned long long fibonacci(long long n, unsigned long long Mod) {unsigned long long m2 = 1, m1 = 1, m0 = 0;unsigned long long x2 = 1, x1 = 0, x0 = 1;while (n > 0) {if (n & 1) {auto a2 = (modmult(x2, m2, Mod) + modmult(x1, m1, Mod)) % Mod;auto a1 = (modmult(x2, m1, Mod) + modmult(x1, m0, Mod)) % Mod;auto a0 = (modmult(x1, m1, Mod) + modmult(x0, m0, Mod)) % Mod;x2 = a2, x1 = a1, x0 = a0;}n >>= 1;if (n > 0) {auto a2 = (modmult(m2, m2, Mod) + modmult(m1, m1, Mod)) % Mod;auto a1 = (modmult(m2, m1, Mod) + modmult(m1, m0, Mod)) % Mod;auto a0 = (modmult(m1, m1, Mod) + modmult(m0, m0, Mod)) % Mod;m2 = a2, m1 = a1, m0 = a0;}}return x1 % Mod;}void fib(long long n, mint &a, mint &b) {if (n == -1) {a = 1, b = 0;return;} else if (n <= 2) {assert(n >= 0);a = (n + 1) / 2, b = (n + 2) / 2;return;}fib(n / 2 - 1, a, b);a *= a, b *= b;mint c = b + a, d = b * 4 - a + (n / 2 % 2 ? -2 : 2);if (n % 2)a = d, b = d + d - c;elsea = d - c, b = d;}int main() {long long X;while (~scanf("%lld", &X)) {ll n = fibonacci(X, (ll)mint::Mod * mint::Mod - 1);mint a, b;fib(n, a, b);mint ans = a;printf("%d\n", ans.get());}return 0;}