矩阵乘法&矩阵快速幂&矩阵快速幂解决线性递推式

矩阵乘法,顾名思义矩阵与矩阵相乘,

两矩阵可相乘的前提:第一个矩阵的行与第二个矩阵的列相等

相乘原则:

a b     *     A B   =   a*A+b*C  a*c+b*D

c d        C D   =   c*A+d*C  c*A+d*C

上代码

 struct matrix
{
ll a[maxn][maxn];
};
matrix matrix_mul(matrix x,matrix y)
{
matrix temp;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
temp.a[i][j]=;
for(int k=;k<=n;k++)
{
temp.a[i][j]+=(x.a[i][k]*y.a[k][j])%mod;
temp.a[i][j]%=mod;
}
}
return temp;
}

∵矩阵乘法满足结合律(不满足交换律)

∴可用快速幂

矩阵快速幂与一般快速幂极其相似,只是把两个数相乘改成了两个矩阵相乘(用个相乘函数即可),所以完全可以按照快速幂的写法来写;

matrix matrix_pow(matrix a,ll b)
{
matrix v;
for(int i=;i<=n;i++) v.a[i][i]=; //初始化,就和把数字初始化成 1 一样,矩阵这样初始化
while(b>)
{
if(b&) v=matrix_mul(v,a);
a=matrix_mul(a,a);
b=b>>;
}
return v;
}

※矩阵快速幂解决线性递推式

举个栗子(我有一盆栗子随便举) 斐波那契序列 (F[n]=F[n-1]+F[n-2])

很多童鞋知道矩阵快速幂可解决斐波那契序列,但并不知道原因

事实上矩阵快速幂可以解决绝大多数线性递推式(不敢说所有=-=,万一呢)

对于斐波那契,递推矩阵(自己起的=-=)为

1 1

0 1

具体推导初始矩阵过程如下(方法不唯一):(以斐波那契额为例)

我们要做的是使F[n-1]+F[n-2]乘某个矩阵得出第一项为F[n](个人理解的=-=)

则 F[n]     =  a  b   *   F[n-1]

F[n-1]      c  d        F[n-2]

∵F[n]=F[n-1]+F[n-2]

则可得 F[n-1]+F[n-2] = a  b   *  F[n-1]

    F[n-1]      c  d    F[n-2]

设F[n-1]为A,F[n-2]为B

则为 A+B  = a  b   *   A    =   a*A+b*B   (将右边矩阵乘开了)

B       c  d   *   B         c*A+d*B

则可以看到 a*A+b*B=A+B

      c*A+d*B=B

很容易看出a=1,b=1,c=0,d=1

所以递推矩阵为

1 1

0 1

普通斐波那契F[1]=1,F[2]=1;

那为什么可以用矩阵快速幂呢?

设上边的0,1为A,斐波那契初始矩阵为B,当N》=2的时候我们可以求斐波那契

比如斐波那契的3项就应该是

A*A*B即可(因为N大于等于2所以要把求得项数减去1然后再乘)

类似的我们可以求斐波那契的第N项

即A*A*A*......*A*B一共乘N-1项。

这个时候我们发现都是乘法耶~那我们就快速幂把,好~快速幂所以我们就完成了快速幂。

所以每一n-1幂所对应的F[n]就是答案,

但F[1]与F[2]为其他数呢,就不能只是这样做了

∵矩阵乘法满足交换律

∴现将递推矩阵进行n次幂运算

再使其乘 F[1] 矩阵,即可得出答案=-=

     F[2]

上一篇:置换贴图 Displacement Mapping


下一篇:hdu 1757 A Simple Math Problem (构造矩阵解决递推式问题)