Matrix Exponentiation - Fibonacci - VNOJ: VNOI Online Judge

Matrix Exponentiation - Fibonacci

Điểm: 0,40

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

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

Input: stdin

Output: stdout

Người đăng:

toha

Nguồn bài:

Matrix Exponentiation

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hãy tìm phần dư của phép chia lấy dư số Fibonacci thứ ~n~ cho ~10^9+7~.

Số Fibonacci thứ ~n~ ~(F_n)~ được xác định bởi dãy truy hồi sau:

~F_0 = 0, F_1 = 1~

~F_n = F_{n-1} + F_{n-2}\ (\forall n \geq 2)~

Input

Gồm ~1~ dòng chứa số nguyên ~n~ ~(0 \leq n \leq 10^{18})~.

Output

Phần dư của phép chia ~F_n~ cho ~10^9 + 7~.

Sample 1

Input

Output

Sample 2

Input

Output

Sample 3

Input

Output

586268941

~F_{50} = 12586269025 \equiv 586268941~ ~(mod ~ ~10^9 + 7)~.

Note

Một vài số hạng đầu tiên của dãy số Fibonacci là ~(0,1,1,2,3,5,8,13,…)~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

1
vominhmanh10 đã bình luận lúc 26, Tháng 11, 2025, 12:07 ← chỉnh sửa →
dựa vào công thức ma trận:
[[F(n + 1), F(n)], [F(n), F(n - 1)]] = [[1, 1], [1, 0]]^n

ta có công thức nhân đôi F(2 * n) = F(n) * (2 * F(n - 1) + F(n)) = F(n) * (2 * F(n + 1) - F(n)),
F(2 * n + 1) = F(n) ^ 2 + F(n + 1) ^ 2

vậy ta tính F(n), F(n + 1) chỉ lấy F(n // 2), F(n // 2 + 1) cứ như thế trong O(log n)

import sys input = sys.stdin.readline def solve(n): if n == 0: return 0, 1 a, b = solve(n // 2) c = (a * (2 * b - a)) % mod d = (a * a + b * b) % mod if n % 2 == 0: return c, d return d, (c + d) % mod mod = 10**9 + 7 if __name__ == "__main__": n = int(input()) print(solve(n)[0] % mod)

0

haitin9Aps đã bình luận lúc 23, Tháng 7, 2025, 2:34

có cao nhân nào chỉ em với, em dùng nhân ma trận vẫn không được full AC

-9

haitin9Aps đã bình luận lúc 23, Tháng 7, 2025, 2:37

include<bits/stdc++.h>

using namespace std;

define MOD 1000000007LL

void matran(long long a[2][2], long long f[2][2]) { long long res[2][2]; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) { res[i][j] = 0; for (int k = 0; k < 2; ++k) res[i][j] = res[i][j] % MOD + ((a[i][k] % MOD) * (f[k][j % MOD)) % MOD; } for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) a[i][j] = res[i][j];

} void power(long long f[2][2], long long n) { long long a[2][2] = {{1,0}, {0,1}}; while(n > 0) { if (n % 2 == 1) matran(a, f); matran(f, f); n/=2; } for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) f[i][j] = a[i][j]; } long long fibonacci(long long n) { if (n == 0) return 0; long long f[2][2] = {{1, 1}, {1, 0}}; power(f, n - 1); return f[0][0]; } int main() { long long n; cin >> n; cout << fibonacci(n); return 0; }

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-24

chunguyen2k8 đã bình luận lúc 1, Tháng 4, 2024, 12:25

Bài dễ quá :3

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-61

nogo007akapkn đã bình luận lúc 3, Tháng 3, 2024, 16:51

xin 1 downvote ạ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.