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

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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#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<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int k=0;k<n;k++)
            {
                temp.a[i][j]+=x.a[i][k]*y.a[k][j];
                temp.a[i][j]=(temp.a[i][j]+mod)%mod;
            }
        }
    }
    return temp;
}

matrix matmod(matrix a,int k)
{
    matrix res;

    memset(res.a,0,sizeof res.a);
    for(int i=0;i<n;i++)res.a[i][i]=1;

    while(k)
    {
        if(k&1)
        res=multiply(res,a);
        k>>=1;
        a=multiply(a,a);
    }
    return res;
}

matrix sum(matrix b,matrix c)
{
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        b.a[i][j]+=c.a[i][j];
        b.a[i][j]%=mod;
    }
    return b;
}

matrix A,B,C;
matrix bin(int k)
{
    if(k<=1)return origin;
    if(k&1)
    {
        A = bin(k-1);
        B = matmod(origin,k);
        return sum(A,B);
    }
    else
    {
        A = bin(k/2);
        B = matmod(origin,k/2);
        C = multiply(B,A);
        return sum(A,C);
    }
}
int main()
{
    int k;

    while(scanf("%d%d%d",&n,&k,&mod)!=EOF)
    {
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        scanf("%d",&origin.a[i][j]);

        matrix ans = bin(k);

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            printf("%d%c",ans.a[i][j]%mod,j==n-1?'\n':' ');
        }
    }
    return 0;
}