Dãy số Fibonacci - LCOJ: Luyện Code Online Judge

BIGFIBO - Dãy số Fibonacci

Điểm: 2,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Dãy số Fibonacci được định nghĩa bởi công thức:

$$\left\{ \begin{array}{l}{F_0} = {F_1} = 1\\{F_n} = {F_{n - 1}} + {F_{n - 2}},\forall n \ge 2\end{array} \right.$$

Yêu cầu: Cho số nguyên không âm ~n~, hãy tính ~F_n~.

Input

Một dòng duy nhất chứa số nguyên không âm ~n~.

Giới hạn:

~0 ≤ n ≤ 10^{18}~.

Output

Một dòng duy nhất chứa số nguyên là phần dư của ~F_n~ khi chia cho ~10^9 + 7~.

Sample

Input #1

Output #1

Input #2

Output #2

836311896

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7;

struct Matrix {
    ll m[2][2];
    Matrix() {
        m[0][0] = m[0][1] = m[1][0] = m[1][1] = 0;
    }
};

Matrix mul(Matrix a, Matrix b) {
    Matrix res;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j] % MOD) % MOD;
    return res;
}

Matrix power(Matrix a, ll n) {
    Matrix res;
    res.m[0][0] = res.m[1][1] = 1;
    while (n) {
        if (n % 2) res = mul(res, a);
        a = mul(a, a);
        n /= 2;
    }
    return res;
}

int main() {
    ll n;
    cin >> n;
    if (n == 0 || n == 1) {
        cout << 1 << endl;
        return 0;
    }
    Matrix base;
    base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;
    base.m[1][1] = 0;
    Matrix res = power(base, n - 1);
    ll Fn = (res.m[0][0] + res.m[0][1]) % MOD;
    cout << Fn << endl;
}

tham khảo

0

______ đã bình luận lúc 5, Tháng 10, 2024, 8:21

n + 1 mà đề bịp=))

2

dinhvantung0611 đã bình luận lúc 25, Tháng 2, 2024, 8:48

Để AC bài này (với cách làm của mình): Ta sử dụng phương pháp tìm số Fib thứ n = Luỹ thừa nhị phân kết hợp với nhân ma trận O(log(n)) (trên mạng có nhé các bạn có thể tìm hiểu). Còn code tuyến tính O(n) sẽ bị TLE.

8

thangtrung1101 đã bình luận lúc 24, Tháng 7, 2023, 1:52

f(0) = f(1) = 1 mà bạn, chắc bạn nhầm rằng f(0) = 0.