Giải bài toán với chu kì Pisano

anhtu1197 · May 29, 2018, 1:24pm

Đây là bài toán em đang gặp trong khóa học mong mọi người giúp đỡ
Input: Nhập n ( <= n <= 10^18) và m ( 2 <= m <= 10^5)
Output: là số fibonacii F[n] chia lấy dư với m;
Theo hướng dẫn thì người ta dùng dãy số pisano để tính (vì số fibonancii có thể lên rất lớn) nhưng em vẫn k hiểu quy luật để tìm ra dãy số đấy Mọi người có thể giúp em được không ạ?
Trên diễn đàn cũng có 1 bài viết như thế này rồi nhưng câu trả lời không đúng theo cách này

Nguyen_Khuyen · July 7, 2016, 2:59pm

Dùng nhân ma trận ý.

phamtrongthang · July 7, 2016, 3:50pm

Bắt đầu mỗi chu kì là 0 và kế tiếp là 1, bạn dùng cái này để cắt chuỗi chu kì. Ta cũng có 1 quy luật khi tính con số tiếp theo của chuỗi tương tự fibonacci: fn = f(n-1) + f(n-2) đó là : fn mod k ={ [ f(n-1) mod k ] + [ f(n-2) mod k ] } mod k ; nói cho dễ hiểu thì lấy 2 số trc trong chuỗi cộng lại rồi modulo cho số k (trong bài là m).
ví dụ f15 mod 3 nó bằng 2+2 mod 3.
Sau khi giải quyết dc đô dài chuỗi rồi thì cái còn lại coi như đơn giản rồi.
+không liên quan: bạn học khóa gì vậy ?

Gio · July 8, 2016, 10:48am

Chu kì pisano m thường lớn hơn m, và phức tạp hơn nhiều so với nhân ma trận. Trừ khi n cực lớn cỡ vài trăm ngàn chữ số thì lúc đó việc tìm chu kì pisano mới hiệu quả

minhcanhtu · October 27, 2018, 1:16am

Không biết bạn còn tham gia diễn đàn nữa không nhỉ? ^^
Mình cũng đang gặp bài này, và mình chưa hiểu chỗ này bạn nói lắm! Mình dùng 01 để cắt chuỗi chu kỳ cụ thể bằng cách nào ạ ?
Và kết hợp với quy luật bạn viết bên dưới như thế nào để với max n = 10^18 ko bị TLE trong 1s ?

rogp10 · October 27, 2018, 3:34am

Dùng ma trận có thể tính ra với 3log2(n) + O(1) phép nhân (hai số giống nhau), vì vậy tính theo ma trận vẫn hay hơn. Cái chu kì thì chắc không dùng được thuật toán vì hai số cộng lại mới ra được một.

minhcanhtu · October 27, 2018, 1:50am

Em chưa học tới chương trình toán THPT nên có vẻ khá khó để áp dụng nhân ma trận anh
Mà theo đề của em thì giới hạn n <= 10^18 và m <= 10^3 thì có thể dùng chu kỳ pisano đó ổn ko ạ?

rogp10 · October 27, 2018, 7:13pm

Đại số tuyến tính rất là thâm nho (kèm với Tổ hợp còn ghê nữa - generating functions). Vector suy cho cùng cũng chỉ là một cách ghi mà thôi. Phép nhân ma trận có thể phát biểu đơn giản:

ô [i, j] = tích vô hướng (vector dòng i, vector cột j). Ta thấy số cột của toán hạng bên trái phải bằng số dòng bên phải.

Nhắc lại F[0] = 0 và F[1] = 1. Ta setup ma trận [1 1 | 1 0] vì F[2] = 1.
Muốn tính F[2] ta lấy M = [1 1 | 1 0] nhân với [1 | 0] để thu được [1 | 1], tức là [F[2] | F[1]].
Tổng quát thành ma trận M^n = [F[n+1] F[n] | F[n] F[n-1]]. Mà phép nhân ma trận có tính kết hợp nên có thể tính kiểu bình phương-nhân. Hay nói cách khác, để tính F[n+1] thì phải tính M^n.

Với tính chất kết hợp trên, suy ra được ngay F[2n] = F[n+1]F[n] + F[n]F[n-1] = (F[n+1] - F[n-1])(F[n+1] + F[n-1]) = F[n+1]^2 - F[n-1]^2. Tương tự với F[2n+1]. Nhưng đệ quy trực tiếp trên đó có khi còn tệ hơn tính thường vì T(2n) = 2T(n) + O(1), công thức của đấu loại trực tiếp

Theo một hướng khác, khi chỉ có thể bước 1 bậc hay 2 bậc thang thì có cả thảy F[n+1] cách bước chân để leo n bậc cầu thang. Vậy để bước 2n bậc thì hoặc là dừng ở bậc thứ n hoặc bậc thứ n-1, rồi bước lên n+1. Do lộ trình khả dĩ bắt buộc phải qua một trong hai bậc đó nên cộng lại như trên.

sauce: https://math.stackexchange.com/a/11527

Kết luận: Giờ ta có thể bỏ qua ma trận để chỉ còn:
F[2n] = F[n+1]^2 - F[n-1]^2
F[2n+1] = F[n+1]^2 + F[n]^2.
F[2n-1] = F[2n+1] - F[2n]
Đúng vậy, 3 phép nhân