POJ 3233 Matrix Power Series (矩阵快速幂 + 二分)

题目大意：

给定矩阵 A；

求A^1 + A^2 + A^3 + .....A^K

利用快速幂的思想

sum (6) =A^1 + A^2 + A^3 + A^3*(A^1 + A^2 + A^3)...

所以可得通项

sum(n)

if(n&1)

{

sum(n) = sum(n-1) * A^n;

}

else sum (n) = sum (n/2) + A(n/2) * sum(n/2);

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define N 30 typedef long long LL; using namespace std; int n,mod; struct matrix { int a[N][N]; }origin; matrix multiply(matrix x,matrix y) { matrix temp; memset(temp.a,0,sizeof(temp.a)); for(int i=0;i
       
        >=1; a=multiply(a,a); } return res; } matrix sum(matrix b,matrix c) { for(int i=0;i