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