bài này nếu dùng đệ quy thì chắc chắn không được,e nghĩ sẽ dùng ma trận nhưng e cũng chưa biết nếu dùng ma trận sẽ như thế nào,các a thông não giúp e
Tính tổng dãy số tribonacci
Ma trận của Fibo là [1 1 | 1 0] (và vector cột khởi đầu là [1 | 0]). Từ đây bạn có thể suy ra ma trận Tribonacci (vector cột của Tribo sẽ có 3 dòng)
Hãy chắc chắn bạn đã hiểu câu dưới này nghĩa là gì
[Fibn+1 | Fibn] = [1 1 | 1 0] * [Fibn | Fibn-1]
(vâng, đúng là lấy dòng * cột )
Còn tổng từ 1 đến N thì bạn biến đổi T(n) thành một hiệu sau đó + vế theo vế sao cho nó tự triệt tiêu bên trong.
https://echo.notable.md/60fe74bc21b5f28f39acc7b2e1eab260821d5d71
viết thử
:V
dãy số cần tìm: A089068
các dãy số liên quan: A001590 A000073
điều kì lạ A089068 liên kết A000073 và A001590 @_@ trong khi tổng dãy Fibo ko thấy dính dáng tới dãy Lucas thì phải :V
a sửa giúp e code này sao lại quá time trên spoj
link đề spoj: https://www.spoj.com/PTIT/problems/SSAM019I/
link code : https://www.ideone.com/v42gHV
Làm vậy còn tệ hơn là 2Tn - Tn-3 đó. Bạn phải áp dụng bình phương - nhân mới được.
modulo 10^15 lận nhân ma trận làm gì có int128_t để chứa phép nhân 2 số 10^15 nhỉ :V Chả lẽ xài __int128 à :V
Chia làm hai nửa để nhân vậy.
__uint128
nó okie hơn.
xài __int128 được, nó cho gcc 8.3 =]