poj 3233 Matrix Power Series

点击打开poj 3233

思路: 二分求和+矩阵快速幂

分析:

1 题目给定一个n*n的矩阵A，要求(A+A^2+....A^K)%m后的矩阵

2 对于任意的A^x，我们都能够利用矩阵快速幂求出，但是我们现在要求的是和。

   仔细观察整个式子，那么我们可以对原式进行变形

   如果k为偶数，那么(A+A^2+....A^K) = (A+...+A^K/2)+A^K/2*(A+...+A^K/2)

   如果k为奇数，那么(A+A^2+....A^K) = (A+...+A^K/2)+A^K/2*(A+...+A^K/2)+A^k

3 那么对于上面的式子的变形，就是二分的思想，那么我们可以利用二分来求和，然后对于单个的矩阵的x次方我们利用快速幂

代码:

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-08-28                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 30;

int n , k , MOD;
struct Matrix{
    int mat[N][N];
    Matrix operator*(const Matrix& m)const{
        Matrix tmp;
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                tmp.mat[i][j] = 0;
                for(int k = 0 ; k < n ; k++)
                    tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;
                tmp.mat[i][j] %= MOD;
            }
        }
        return tmp;
    }
    Matrix operator+(const Matrix& m)const{
        Matrix tmp;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < n ; j++)
                tmp.mat[i][j] = (mat[i][j]+m.mat[i][j])%MOD;
        return tmp;
    }
};

Matrix Pow(Matrix m , int t){
    Matrix ans;
    memset(ans.mat , 0 , sizeof(ans.mat));
    for(int i = 0 ; i < n ; i++)
        ans.mat[i][i] = 1;
    while(t){
        if(t&1)
            ans = ans*m;
        t >>= 1;
        m = m*m;
    }
    return ans;
}

Matrix solve(Matrix m , int t){
    Matrix A;
    memset(A.mat , 0 , sizeof(A.mat));
    for(int i = 0 ; i < n ; i++)
        A.mat[i][i] = 1;
    if(t == 1)
        return m;
    if(t&1)
        return (Pow(m,t>>1)+A)*solve(m,t>>1)+Pow(m , t);       
    else
        return (Pow(m,t>>1)+A)*solve(m,t>>1);       
}

void output(Matrix ans){
    for(int i = 0 ; i < n ; i++){
        printf("%d" , ans.mat[i][0]%MOD);
        for(int j = 1 ; j < n ; j++)
            printf(" %d" , ans.mat[i][j]%MOD);
        puts("");
    }
}

int main(){
    Matrix m , ans;
    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" , &m.mat[i][j]);
         ans = solve(m , k);
         output(ans);
    }
    return 0;
}