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

深藏阁楼爱情的钟 2022-06-05 12:15 199阅读 0赞

Matrix Power Series

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;3000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;131072K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;24823</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;10304</td> 
  </tr> 
 </tbody> 
</table>

Description

Given a *n* × *n* matrix *A* and a positive integer *k*, find the sum *S* = *A* + *A*2 + *A*3 + … + *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;
    }

[POJ Monthly--2007.06.03]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2007.06.03