斐波那契数列的矩阵推导(看不懂的可以放弃矩阵了)

一.矩阵乘法

设矩阵A,B 满足 :A的列数==B的行数

矩阵乘法的运算规则:

将A矩阵的每一行乘以B矩阵的每一列

*

==

==

二.斐波那契数列的矩阵推导

首先我们想

Fib[i]=Fib[i-1]+Fib[i-2];

所以斐波那契数列的第i项之与两个数也就是Fib[i-1]+Fib[i-2]有关

那么我们可以设第一个矩阵

M1=

因为我们需要利用矩阵推出斐波那契的第n项

所以我们设M1的下一项为M3

则M3=(也就是让M1的下标整体后移一位)

那么现在我们需要一个过渡矩阵M2来实现这个从M1到M3的操作

因为M1是一个1*2的矩阵

M3也是一个1*2的矩阵

那么M2一定是一个2*2的矩阵

(原因:1.M1的列要和M2的行相等

2.M3的列数是2)

设M2=

所以

a*fi-2+b*fi-1==fi-1①

c*fi-2+d*fi-1==fi②

这个式子看上去是不能解的

但是我们想一下

当a==0&&b==1的时候①成立

当c==1&&d==1的时候②成立(Fib[i]=Fib[i-1]+Fib[i-2])

所以我们很容易的得到矩阵M2

M2=

三.一道简单的例题

设fi=fi-1+2fi-2+3fi-3

按照上面的方法求出M1,M2,M3

提示:矩阵推导的时候不带系数

(建议先做再看题解)

解:

设M1=

M3=

则M2一定是一个3*3的矩阵

设M2=

则a*fi-1+b*fi-2+c*fi-3==fi== fi-1+2fi-2+3fi-3

d*fi-1+e*fi-2+f*fi-3==fi-1

g*fi-1+h*fi-2+i*fi-3==fi-2

易得 a==1,b==2,c==3

d==1,e==0,f==0

g==0,h==0,i==0

所以

M2=

时间: 05-05

斐波那契数列的矩阵推导(看不懂的可以放弃矩阵了)的相关文章

斐波那契数列F(n)【n超大时的(矩阵加速运算) 模板】

hihocoder #1143 : 骨牌覆盖问题·一 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 骨牌,一种古老的玩具.今天我们要研究的是骨牌的覆盖问题: 我们有一个2xN的长条形棋盘,然后用1x2的骨牌去覆盖整个棋盘.对于这个棋盘,一共有多少种不同的覆盖方法呢? 举个例子,对于长度为1到3的棋盘,我们有下面几种覆盖方式: 提示:骨牌覆盖 提示:如何快速计算结果 输入 第1行:1个整数N.表示棋盘长度.1≤N≤100,000,000 输出 第1行:1个整数,表示

快速求斐波那契数列(矩阵乘法+快速幂)

斐波那契数列 给你一个n:f(n)=f(n-1)+f(n-2) 请求出 f(f(n)),由于结果很大请 对答案 mod 10^9+7; 1<=n<=10^100; 用矩阵乘法+快速幂求斐波那契数列是经典应用: 矩阵公式 C i j=C i k *C k j; 根据递推式 构造2*2矩阵: 原始矩阵 1 0 0 1 矩阵 2 1 1 1 0 原始矩阵与矩阵 2相乘达到转化状态效果: 对矩阵二进行快速幂 乘法:达到快速转化矩阵的效果: 即使达到快速转化状态:那么大的数据范围也很难求解: 高精?这有

【矩阵快速幂】HDU 4549 : M斐波那契数列(矩阵嵌套)

[题目链接]click here~~ [题目大意] M斐波那契数列F[n]是一种整数数列,它的定义如下: F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 ) 现在给出a, b, n,你能求出F[n]的值吗?对每组测试数据请输出一个整数F[n],由于F[n]可能很大,你只需输出F[n]对1000000007取模后的值即可,每组数据输出一行. [Source] :2013金山西山居创意游戏程序挑战赛――初赛(2) [解题思路] 这个题稍微有点难度,就

HDU 4549 M斐波那契数列(矩阵快速幂)

Problem Description M斐波那契数列F[n]是一种整数数列,它的定义如下: F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 ) 现在给出a, b, n,你能求出F[n]的值吗? Input 输入包含多组测试数据: 每组数据占一行,包含3个整数a, b, n( 0 <= a, b, n <= 10^9 ) Output 对每组测试数据请输出一个整数F[n],由于F[n]可能很大,你只需输出F[n]对1000000007取模

hdu 4549 M斐波那契数列(快速幂 矩阵快速幂 费马小定理)

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=4549: 题目是中文的很容易理解吧.可一开始我把题目看错了,这毛病哈哈. 一开始我看错题时,就用了一个快速幂来解,不用说肯定wa,看题目的通过率也不高,我想会不会有啥坑啊.然而我就是那大坑,哈哈. 不说了,直接说题吧,先讨论k=1,2,3;时的解.这应该会解吧,不多说了: 从第四项开始f(4)=a^1+b^2;f(5)=a^2+b^3;f(6)=a^3+b^5......; 看出来了吧,a上的指数成斐波

#斐波那契数列用矩阵快速幂求解f(n)#

通常情况下,斐波那契数列第n项可以通过递归求解或者直接求解但当n非常大的时候,求解f(n)将显得非常困难下面利用矩阵以及快速幂的方法在logn复杂度内求解 则可以运用快速幂来求解矩阵高次幂,复杂度降为logn 来自为知笔记(Wiz)

poj 3070 Fibonacci (矩阵快速幂求斐波那契数列的第n项)

题意就是用矩阵乘法来求斐波那契数列的第n项的后四位数.如果后四位全为0,则输出0,否则 输出后四位去掉前导0,也...就...是...说...输出Fn%10000. 题目说的如此清楚..我居然还在%和/来找后四位还判断是不是全为0还输出时判断是否为0然后 去掉前导0.o(╯□╰)o 还有矩阵快速幂的幂是0时要特判. P.S:今天下午就想好今天学一下矩阵乘法方面的知识,这题是我的第一道正式接触矩阵乘法的题,欧耶! #include<cstdio> #include<iostream>

斐波那契数列以及斐波那契数列的衍生形式 利用矩阵快速幂求解

一.斐波那契数列F[n]=F[n-1]+F[n-2] 可转换为矩阵s[1,1,1,0]的n次幂的矩阵的s[0][1]的值 矩阵的幂次方 可通过 奇判断及进制移位提高时间效率 位与运算 n&1表示的意思:取二进制n的最末位,二进制的最末位为零表示n为哦数,为1表示奇数,即等价于n%2 n>>1 是将n的二进制向右移动一位, n>>=1 即把移动后的值赋给n 题目:求斐波那契数列F[n]%10000(取模) #include <cstdio> #include &l

矩阵乘法快速幂 codevs 1574 广义斐波那契数列

codevs 1574 广义斐波那契数列 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 广义的斐波那契数列是指形如an=p*an-1+q*an-2的数列.今给定数列的两系数p和q,以及数列的最前两项a1和a2,另给出两个整数n和m,试求数列的第n项an除以m的余数. 输入描述 Input Description 输入包含一行6个整数.依次是p,q,a1,a2,n,m,其中在p,q,a1,a2整数范围内,n和m在长整数范围