Phép nhân ma trận với Fibo: [1 1 | 1 0] * [F_1] | F_0] = [F_2 | F_1], hay [F_(n+1) | F_n] = [1 1 | 1 0]^n * [1 | 0]. Từ đây ta thiết lập đẳng thức ma trận Q_n = [1 1 | 1 0] ^ n = [F_(n+1) F_n | F_n F_(n-1)] (n nguyên dương) dễ dàng. (kiểm tra: F_1 = 1, F_0 = 0) vì [1 | 0] là vector cột của Q_1.
Ta có 1 kết quả đẹp mắt: F_(2n) = F_(n+1)^2 - F_(n-1)^2 
dùng hđtđn sẽ trở thành F_(2n) = F_(n) * (F_(n+1) + F_(n-1)). Để tính F_(2n) ta sẽ tính Q_(2n) = Q_n^2, vậy F_(2n) = F_(n+1)F_n + F_n*F_(n-1), đpcm 
[spoiler](Do F_(2n) nằm ở dòng 1 cột 2 nên ta lấy vector dòng 1 nhân với vector cột 2, rồi nhìn dòng 1 thôi) [/spoiler]
Bạn đọc có thể chứng minh bằng tổ hợp nó cũng có liên quan chút chút đến qhđ với công thức truy hồi đã có sẵn. [spoiler]tức là bây h từ lời giải đặt ra bài toán ứng với nó, chứng minh bằng tổ hợp là như vậy.[/spoiler]
Ma trận thì dễ tính: 8 phép nhân hai số với mỗi phép nhân ma trận (hai cột), mà bài này nhân mod k O(1) nên phần tính F_n mod k là O(logn). Cộng thêm phần hash O(k) nữa là O(k+logn). Tính theo ct truy hồi thì ta có T(2n) = 2T(n) + O(1), hay T(n) = O(n), không nên.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?