Skip to content

14071: 【原4071】Fibonacci数列

题目

题目描述

author: Engineev 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4071

Description

面包希望知道大家的计科导课和线性代数课有没有好好上,所以出了这一道题目。(<-这是hint)

大家都知道有一个数列叫做Fibonacci数列,它是这样定义的\(a_0 = a_1 = 1\),\(a_{n+1} = a_n + a_{n-1}\). 面包想要知道Fibonacci的第\(n\)项是多少. 由于结果可能十分大,所以需要你对结果mod \(10^9 + 7\)

Input Format

一个数字\(n\).

Output Format

输出对应的\(a_n % 10^9+7\)即可.

Sample Input

5

Sample Output

8

数据范围

对于70%的数据,确保\(n \le 10^8\).

对于100%的数据,确保\(n \le 10^{18}\)

BugenZhao's solution

//
// Created by BugenZhao on 2019/5/17.
//

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll=long long;
using ull=unsigned long long;

const int P = 1e9 + 7;

class Matrix2D {
public:
    ll a, b, c, d;

    Matrix2D(ll a, ll b, ll c, ll d) :
            a(a), b(b), c(c), d(d) {}
};

Matrix2D operator*(const Matrix2D &x, const Matrix2D &y) {
    ll a = x.a * y.a + x.b * y.c;
    ll b = x.a * y.b + x.b * y.d;
    ll c = x.c * y.a + x.d * y.c;
    ll d = x.c * y.b + x.d * y.d;
    return Matrix2D(a % P, b % P, c % P, d % P);
}

Matrix2D pow(const Matrix2D &m, ull p) {
    if (p == 0) return Matrix2D(1, 0, 0, 1);
    if (p == 1) return m;
    Matrix2D tmp = pow(m, p / 2);
    if (p % 2) return tmp * tmp * m;
    else return tmp * tmp;
}

int main() {
    ull n;
    cin >> n;
    Matrix2D ans = pow(Matrix2D(1, 1, 1, 0), n);
    cout << ans.a << endl;
    return 0;
}

FineArtz's solution

/* Fibonacci数列 */
#include <iostream>
using namespace std;

const long long MOD = 1000000007;

class matrix{
public:
    matrix(long long a, long long b, long long c, long long d)
    : a11(a), a12(b), a21(c), a22(d) {}
    matrix(const matrix &a) : a11(a.a11), a12(a.a12), a21(a.a21), a22(a.a22) {}
    long long a11, a12, a21, a22;
};
inline matrix operator *(const matrix &m1, const matrix &m2){
    matrix ret(0, 0, 0, 0);
    ret.a11 = (m1.a11 * m2.a11 % MOD + m1.a12 * m2.a21 % MOD) % MOD;
    ret.a12 = (m1.a11 * m2.a12 % MOD + m1.a12 * m2.a22 % MOD) % MOD;
    ret.a21 = (m1.a21 * m2.a11 % MOD + m1.a22 * m2.a21 % MOD) % MOD;
    ret.a22 = (m1.a21 * m2.a12 % MOD + m1.a22 * m2.a22 % MOD) % MOD;
    return ret;
}
matrix pow(matrix x, long long n){
    matrix ret(1, 0, 0, 1), t(x);
    while (n != 0){
        if (n & 1){
            ret = ret * t;
        }
        t = t * t;
        n >>= 1;
    }
    return ret;
}
int main(){
    long long n;
    cin >> n;
    matrix f(1, 1, 1, 0);
    f = pow(f, n + 1);
    cout << f.a21 << endl;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
using namespace std;

constexpr long long mod = (long long)(1e9 + 7);

class matrix {
public:
    long long a11 = 0, a12 = 0;
    long long a21 = 0, a22 = 0;

    matrix() = default;
    matrix(long long a11, long long a12, long long a21, long long a22) :a11(a11% mod), a12(a12% mod)
        , a21(a21% mod), a22(a22% mod) {}

    matrix(matrix&& other){
        swap(*this, other);
    }

    void operator=(matrix&& other) {
        swap(*this, other);
    }

    matrix&& operator*(const matrix& b) const{
        matrix temp;
        temp.a11 = (a11 * b.a11 + a12 * b.a21) % mod;
        temp.a12 = (a11 * b.a12 + a12 * b.a22) % mod;
        temp.a21 = (a21 * b.a11 + a22 * b.a21) % mod;
        temp.a22 = (a21 * b.a12 + a22 * b.a22) % mod;
        return std::move(temp);
    }
};

matrix&& fast_pow(const matrix& a, long long b) {
    matrix ans(1, 0, 0, 1), base(a.a11, a.a12, a.a21, a.a22);
    for (; b; b >>= 1) {
        if (b & 1LL)
            ans = ans * base;
        base = base * base;
    }
    return std::move(ans);
}

int main() {
    long long n;
    scanf("%lld", &n);

    matrix temp(1, 1, 0, 0);
    matrix to(1, 1, 1, 0);
    matrix ans;
    ans = temp * fast_pow(to, n - 1);
    printf("%lld", ans.a11);

    return 0;
}

q4x3's solution

/**
 * 矩阵快速幂求斐波那契
 **/
#include <iostream>
#define ll long long

using namespace std;

const ll mo = 1e9 + 7;

struct mat {
    ll a11, a12, a21, a22;
    mat():a11(0), a12(1), a21(1), a22(1) {}
    mat operator*(const mat &other) const {
        mat tmp;
        tmp.a11 = (a11 * other.a11 % mo + a12 * other.a21 % mo) % mo;
        tmp.a12 = (a11 * other.a12 % mo + a12 * other.a22 % mo) % mo;
        tmp.a21 = (a21 * other.a11 % mo + a22 * other.a21 % mo) % mo;
        tmp.a22 = (a21 * other.a12 % mo + a22 * other.a22 % mo) % mo;
        return tmp;
    }
};

mat binary_pow(ll n) {
    mat tmp, cache;
    tmp.a11 = 1; tmp.a12 = 0; tmp.a21 = 0; tmp.a22 = 1;
    while(n > 0) {
        if(n & 1) {
            tmp = tmp * cache;
        }
        cache = cache * cache;
        n >>= 1;
    }
    return tmp;
}

ll n;

int main() {
    cin >> n;
    mat a = binary_pow(n);
    printf("%lld\n", a.a22);
}

skyzh's solution

#include <iostream>
using namespace std;

struct Matrix2x2 {
    unsigned long long s[2][2];
};

const int S = 1e9 + 7;

Matrix2x2 mul(const Matrix2x2 &a, const Matrix2x2 &b) {
    Matrix2x2 c;
    /*
     * a 0 1 b 0 1
     * a 2 3 b 2 3
     */
    c.s[0][0] = (a.s[0][0] * b.s[0][0] + a.s[0][1] * b.s[1][0]) % S;
    c.s[0][1] = (a.s[0][0] * b.s[0][1] + a.s[0][1] * b.s[1][1]) % S;
    c.s[1][0] = (a.s[1][0] * b.s[0][0] + a.s[1][1] * b.s[1][0]) % S;
    c.s[1][1] = (a.s[1][0] * b.s[0][1] + a.s[1][1] * b.s[1][1]) % S;
    return c;
}

unsigned long long fab(unsigned long long n) {
    Matrix2x2 base, f;
    base.s[0][0] = 1;
    base.s[0][1] = 1;
    base.s[1][0] = 0;
    base.s[1][1] = 0;
    f.s[0][0] = 1;
    f.s[0][1] = 1;
    f.s[1][0] = 1;
    f.s[1][1] = 0;
    while (n > 0) {
        if (n & 1) base = mul(base, f);
        f = mul(f, f);
        n >>= 1;
    }
    return base.s[0][1];
}
int main() {
    unsigned long long N;
    cin >> N;
    cout << fab(N) << endl;
    return 0;
}

victrid's solution

#include <cstdio>
#include <iostream>
#define mod 1000000007LL
using namespace std;
struct matrix {
    long long a1, a2, b1, b2;
    matrix operator*(const matrix& rhs) {
        return matrix{(a1 * rhs.a1 + a2 * rhs.b1) % mod, (a1 * rhs.a2 + a2 * rhs.b2) % mod, (b1 * rhs.a1 + b2 * rhs.b1) % mod, (b1 * rhs.a2 + b2 * rhs.b2) % mod};
    }
};
matrix fibo{1, 1, 1, 0};
matrix init{1, 0, 0, 1};
int main() {
    long long n;
    scanf("%lld", &n);
    for (long long i = n - 1; i; i >>= 1) {
        if (i & 1LL)
            init = fibo * init;
        fibo = fibo * fibo;
    }
    printf("%lld", (init.a1 + init.a2) % mod);
    return 0;
}