首页 > 代码库 > 模板C++ 02数论算法 4矩阵乘法

模板C++ 02数论算法 4矩阵乘法

2024-10-01 19:12:39   219人阅读

矩阵乘法：用来求某种 递推关系。

矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。

定义

设A为A*M的矩阵，B为M*B的矩阵，那么矩阵C为矩阵A与B的乘积，其中矩阵C中的第i行第j列元素可以表示为：

技术分享

如下所示：

技术分享

开一个2*2的矩阵：主要是为了快速幂的方便，一个可以和自己乘上许多次（>=2）的矩阵只有可能是正方形的，所以要开这样一个矩阵。

【题目描述】

a[1]=a[2]=a[3]=1

a[x]=a[x-3]+a[x-1]  (x>3)

求a数列的第n项对1000000007（10^9+7）取余的值。

【输入格式】

第一行一个整数T，表示询问个数。

以下T行，每行一个正整数n。

【输出格式】

每行输出一个非负整数表示答案。

【样例输入】3 6 8 10

【样例输出】4 9 19

【数据范围】对于100%的数据 T<=100，n<=2*10^9；

然后就是使用矩阵乘法来递推。

如果想要预处理，也是可以的，只不过T<=100，所以偷懒省空间。

struct mod
{
    long long a[4][4];
    mod() { memset(a,0,sizeof(a)); }
};
mod mul(mod a,mod b)//矩阵乘法
{
    mod c;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%1000000007;
    return c;
}
void make(int n)
{
    mod a,c;
    c.a[1][1]=1;c.a[2][1]=1;c.a[3][1]=1;
    a.a[1][1]=0;a.a[1][2]=1;a.a[1][3]=0;
    a.a[2][1]=0;a.a[2][2]=0;a.a[2][3]=1;
    a.a[3][1]=1;a.a[3][2]=0;a.a[3][3]=1;
    n++;
    while(n>0)//快速幂
    {
        if(n&1) c=mul(c,a);//不能是mul(a,c)
        a=mul(a,a);//(A^n)*B
        n>>=1;
    }
    printf("%d\n",c.a[3][3]%1000000007);
}
int main(int argc,char *argv[])
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        make(n);
    }
}

 

模板C++ 02数论算法 4矩阵乘法


联系
我们