矩阵构造学习笔记

发布于 2019-07-05  60 次阅读


Fibonacci数列的第n项快速求法

Fibonacci数列:F(0)=1,F(1)=1,F(n)=F(n-1)+F(n-2)

解法:

构造一个矩阵,使用矩阵快速幂进行运算,速度可以极大的提高。

考虑1×2的矩阵【f[n-2],f[n-1]】。根据Fibonacci数列的递推关系,我们可以通过乘以一个2×2的矩阵A,得到矩阵:【f[n-1],f[n]】。

img

我们可以发现这道题目的推导是这样的

由 F[i-1] , F[i-2] , 这个状态 推至 F[i] , F[i-1] , F[i-2]

通过这个推导我们可以发现:

f[i]=f[i-1]*1+f[i-2]*1;

所以矩阵的第一列应该是 1 1;

f[i-1]=f[i-1]*1+f[i-2]*0;

所以矩阵的第二列应该是 1 0;

于是我们就得到了一个2*2的初始矩阵,直接进行快速幂就可以了

例题:

题目地址

代码如下:

#include<iostream>
#include<cstdio>
#define int long long
#define mod 1000000007

using namespace std;

struct Mat
{
    int m[101][101];
};
Mat a,e;
int cnt;
Mat Mul(Mat x,int n,Mat y,int m,int tmp)
{
    Mat c;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            c.m[i][j]=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            for (int k=1;k<=tmp;k++)
                c.m[i][j]=c.m[i][j]%mod+x.m[i][k]*y.m[k][j]%mod;
    return c;
}
Mat pow(Mat x,int y)
{
    Mat ans=e;
    while (y)
    {
        if (y&1) ans=Mul(ans,2,x,2,2);
        x=Mul(x,2,x,2,2);
        y>>=1;
    }
    return ans;
}
signed main()
{
    cin>>cnt;
    a.m[1][2]=a.m[2][1]=a.m[1][1]=1;
    a.m[2][2]=0;
    for (int i=1;i<=2;i++)
        e.m[i][i]=1;
    Mat ans=pow(a,cnt-1);
    //Mat p;
    //p.m[1][1]=p.m[1][2]=1;
    //ans=Mul(p,1,ans,2,2);
    cout<<ans.m[1][1]%mod<<endl;
    return 0;
}

再来一道类似的题

题目地址

我们可以发现这道题目的推导是这样的

由 F[i-1] , F[i-2] , F[i-3] 这个状态 推至 F[i] , F[i-1] , F[i-2]

通过这个推导我们可以发现:

f[i]=f[i-1]*1+f[i-2]*0+f[i-3]*1;

所以矩阵的第一行应该是 1 0 1;

f[i-1]=f[i-1]*1+f[i-2]*0+f[i-3]*0;

所以矩阵的第二行应该是 1 0 0;

f[i-2]=f[i-1]*0+f[i-2]*1+f[i-3]*0;

所以矩阵的第行列应该是 0 1 0;

所以说 我们通过对前后矩阵的推导,便可以得到一个3*3的矩阵:

img

然后的事情就和上面一样了

#include<iostream>
#include<cstdio>
#define int long long
#define mod 1000000007

using namespace std;

struct Mat
{
    int m[101][101];
};
Mat a,e;
int cnt;
Mat Mul(Mat x,int n,Mat y,int m,int tmp)
{
    Mat c;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            c.m[i][j]=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            for (int k=1;k<=tmp;k++)
                c.m[i][j]=c.m[i][j]%mod+x.m[i][k]*y.m[k][j]%mod;
    return c;
}
Mat pow(Mat x,int y)
{
    Mat ans=e;
    while (y)
    {
        if (y&1) ans=Mul(ans,3,x,3,3);
        x=Mul(x,3,x,3,3);
        y>>=1;
    }
    return ans;
}
signed main()
{
	int t;
	cin>>t;
	for (int ri=1;ri<=t;ri++)
	{
    	cin>>cnt;
    	a.m[1][1]=a.m[2][1]=a.m[1][3]=a.m[3][2]=1;
    	/*
    	1 0 1
    	1 0 0
    	0 1 0
    	*/
    	a.m[1][2]=a.m[2][2]=a.m[2][3]=a.m[3][1]=a.m[3][3]=0;
    	for (int i=1;i<=3;i++)
        	e.m[i][i]=1;
    	Mat ans=pow(a,cnt-1);
    	cout<<ans.m[1][1]%mod<<endl;
	}
    return 0;
}

来一道更毒瘤的题:

首先我们构造一个竖着的向量:

因为n要变到n+1所以我们加一个常数1

然后既可以按照前面的方法愉快的构建矩阵了

注意乘的顺序

Cause this is the life. Living is do or die.