Luogu 3390 【模板】矩阵快速幂（矩阵乘法，快速幂）

Description

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

Input

第一行，n,k

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

Output

输出A^k

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

Sample Input

2 1

1 1

1 1

Sample Output

1 1

1 1

Http

Luogu:https://www.luogu.org/problem/show?pid=3390

Source

矩阵乘法，快速幂

解决思路

关于矩阵和矩阵乘法的内容可以到我的这一篇博客查看。

这一题需要注意的就是初始矩阵的赋值，具体请看代码。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

const int maxN=201;

const ll Mod=1000000007;

const ll inf=2147483647;

int n;

class Matrix

{

public:

    ll M[maxN][maxN];

    Matrix(int x)

    {

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

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

                M[i][j]=x;

    }

    Matrix(ll Arr[maxN][maxN])

    {

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

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

                M[i][j]=Arr[i][j];

    }

    void print()

    {

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

        {

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

                cout<<M[i][j]<<' ';

            cout<<endl;

        }

    }

};

Matrix operator * (Matrix A,Matrix B)

{

    Matrix Ans(0);

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

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

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

                Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod;

    return Ans;

}

ll Arr[maxN][maxN];

ll read();

void Pow(ll Po);

int main()

{

    n=read();

    ll Po=read();

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

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

            Arr[i][j]=read();

    Pow(Po-1);//注意，这里为什么要-1呢，因为我们知道a^1是a，对于矩阵来说就是A^1是A,所以在传进去的时候先-1（相当于已经进行了一次操作），而若Po==1，则在Pow(Po-1)中不会执行循环，此时也正好是矩阵A（仔细揣摩一下）

    return 0;

}

ll read()

{

    ll x=0;

    ll k=1;

    char ch=getchar();

    while (((ch>'9')||(ch<'0'))&&(ch!='-'))

        ch=getchar();

    if (ch=='-')

    {

        k=-1;

        ch=getchar();

    }

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

    {

        x=x*10+ch-48;

        ch=getchar();

    }

    return x*k;

}

void Pow(ll P)

{

    Matrix A(Arr);

    Matrix B(Arr);

    while (P!=0)

    {

        if (P&1)

            A=A*B;

        B=B*B;

        P=P>>1;

    }

    A.print();

    return;

}

巴特西

Luogu 3390 【模板】矩阵快速幂（矩阵乘法，快速幂）

Luogu 3390 【模板】矩阵快速幂（矩阵乘法，快速幂）

Description

Input

Output

Sample Input

Sample Output

Http

Source

解决思路

代码

最新文章

热门文章

巴特西

Luogu 3390 【模板】矩阵快速幂 （矩阵乘法，快速幂）

Luogu 3390 【模板】矩阵快速幂 （矩阵乘法，快速幂）

Description

Input

Output

Sample Input

Sample Output

Http

Source

解决思路

代码

最新文章

热门文章

Luogu 3390 【模板】矩阵快速幂（矩阵乘法，快速幂）

Luogu 3390 【模板】矩阵快速幂（矩阵乘法，快速幂）