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:

Source

矩阵乘法，快速幂

解决思路

关于矩阵和矩阵乘法的内容可以到我的查看。

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

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define ll long longconst 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
         
          '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;}