poj-3233 Matrix Power(构造矩阵+矩阵快速幂)-蒲公英云

poj-3233 Matrix Power(构造矩阵+矩阵快速幂)

Matrix Power Series

Time Limit: 3000MS		Memory Limit: 131072K
Total Submissions: 24823		Accepted: 10304

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample Input

2 2 4
0 1
1 1

Sample Output

1 2
2 3

Source

POJ Monthly—2007.06.03, Huang, Jinsong

思路：常规写无疑会超时，我们会发现S(k)=A(S(k-1))+A

所以可以构造[S(n), E]=[S(n-1), E]*[A, 0 ; A, E]=[S(1), E]*[A, 0 ; A, E]^(n-1)

用矩阵快速幂求出[A, 0 ; A, E]^(n-1)即可；

#include<cstdio>
using namespace std;
int k, n, m;
typedef struct Matrix{
    int a[100][100];
}Matrix;
Matrix A, S;
Matrix mul(Matrix x, Matrix y, int row, int col)
{
    Matrix c;
    for(int i=1; i<=row; i++)
        for(int j=1; j<=col; j++)
    {
        c.a[i][j]=0;
        for(int k=1; k<=col; k++)
            c.a[i][j]=(c.a[i][j]%m + (x.a[i][k]%m)*(y.a[k][j]%m))%m;
    }
    return c;
}
Matrix pow(Matrix x, int t)
{
    Matrix c;
    for(int i=1; i<=2*n; i++)
        for(int j=1; j<=2*n; j++)
            if(i==j)
                c.a[i][j]=1;
            else
                c.a[i][j]=0;
    while(t)
    {
        if(t&1)
        {
            c=mul(c, x, 2*n, 2*n);
        }
        x=mul(x, x, 2*n, 2*n);
        t>>=1;
    }
    return c;
}
int main(){
    scanf("%d%d%d", &n, &k, &m);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            scanf("%d", &A.a[i][j]);
            S.a[i][j]=A.a[i][j];
            A.a[n+i][j]=A.a[i][j];
            A.a[i][n+j]=0;
            i==j? A.a[n+i][n+j]=1:A.a[n+i][n+j]=0;
            i==j? S.a[i][n+j]=1:S.a[i][n+j]=0;
        }
    }
    A=pow(A, k-1);
    S=mul(S, A, n, 2*n);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<n; j++)
            printf("%d ", S.a[i][j]);
        printf("%d\n", S.a[i][n]);
    }
    return 0;
}