题目背景

矩阵快速幂

题目描述

给定n*n的矩阵A，求A^k

输入输出格式

输入格式：

第一行，n,k

第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素

输出格式：

输出A^k

共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7

输入输出样例

输入样例#1：

输出样例#1：

1 1

1 1

说明

n<=100, k<=10^12, |矩阵元素|<=1000 算法：矩阵快速幂

如题，矩阵快速幂。

已知，矩阵乘法：

第一个矩阵：

5 6 7

8 9 4

第二个矩阵：

2 3 7

2 4 8

8 3 6

相乘得：

5*2+6*2+7*8 5*3+6*4+7*3 5*7+6*8+7*6

8*2+9*2+4*8 8*3+9*4+4*3 8*7+9*8+4*6

即：

78 60 125

36 72 152

再利用快速幂可得答案。

最后附上经我们喻队（

PIPIBoss

）指点的代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#define ll long long

using namespace std;

ll read()

{

    ll x=,y=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')

            y=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*y;

}

int n;

ll k;

struct ju

{

    ll a[][];

    inline ju operator *(const ju &b)const//inline用来定义内联函数，即在类中用的函数，可以加快速度。

    {　　　　　　　　　　　　　　　　　　　　　　//该函数的作用是来重载*号运算符。

        ju tmp;

        for(int i=; i<=n; i++)

            for(int j=; j<=n; j++)

            {

                tmp.a[i][j]=;

                for(int k=; k<=n; k++)

                {

                    tmp.a[i][j]+=a[i][k]*b.a[k][j];

                    tmp.a[i][j]%=;

                }

            }

        return tmp;

    }

}ans;

ju pow(ju a,ll k)

{

    ju tmp=a;

    k--;

    while(k)

    {

        if(k&)

            tmp=tmp*a;

        a=a*a;

        k>>=;

    }

    return tmp;

}

int main()

{

    scanf("%d%lld",&n,&k);

    for(int i=; i<=n; i++)

        for(int j=; j<=n; j++)

            ans.a[i][j]=read();

    ans=pow(ans,k);

    for(int i=; i<=n; i++)

    {

        for(int j=; j<=n; j++)

            printf("%lld ",ans.a[i][j]);

        putchar('\n');

    }

    return ;

}

//    FOR C.H.

最后的最后，别忘了加上头文件，我一开始就是因为没加头文件错了几次。

巴特西

P3390 【模板】矩阵快速幂

题目背景

题目描述

输入输出格式

输入输出样例

说明

PIPIBoss

最新文章

热门文章