POJ 3233 Matrix Power Series （矩阵乘法）

Matrix Power Series

Time Limit: 3000MS		Memory Limit: 131072K
Total Submissions: 11954		Accepted: 5105

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10⁹) and m (m < 10⁴). 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

Sample Output

1 2

2 3

Source

POJ Monthly--2007.06.03, Huang, Jinsong

题意：已知一个n*n的矩阵A，和一个正整数k，求S = A + A² + A³ + … + A^k。

思路：矩阵快速幂。首先我们知道 A^x 可以用矩阵快速幂求出来（具体可见poj 3070）。其次可以对k进行二分，每次将规模减半，分k为奇偶两种情况，如当k = 6和k = 7时有：

k = 10 有： S(9) = ( A^1+A^2+A^3+A^4+ A^5 ) + A^5 * ( A^1+A^2+A^3+A^4+A^5 ) = S(5) + A^5 * S(5)

k = 5 有： S(5) = ( A^1+A^2 ) + A^3 + A^3 * ( A^1+A^2 ) = S(2) + A^3 + A^3 * S(2)

　 k = 2 有 : S(2) = A^1 + A^2 = S(1) + A^1 * S(1)

从上面几个式子可以发现，当k为奇数或者偶数的区别，具体见代码中的solve函数。（solve函数的功能：递推到底层，也就是到 k = 1时回退，最后一步一步求出，弄懂递推的思想，这题也就明白了），当然定义成数组，然后再进行一些预处理，效率会更高些。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,k,mod;

struct Matrix{

    int arr[][];

};

Matrix unit,init;

Matrix Mul(Matrix a,Matrix b){

    Matrix c;

    for(int i=;i<n;i++)

        for(int j=;j<n;j++){

            c.arr[i][j]=;

            for(int k=;k<n;k++)

                c.arr[i][j]=(c.arr[i][j]+a.arr[i][k]*b.arr[k][j]%mod)%mod;

            c.arr[i][j]%=mod;

        }

    return c;

}

Matrix Pow(Matrix a,Matrix b,int x){

    while(x){

        if(x&){

            b=Mul(b,a);

        }

        x>>=;

        a=Mul(a,a);

    }

    return b;

}

Matrix Add(Matrix a,Matrix b){

    Matrix c;

    for(int i=;i<n;i++)

        for(int j=;j<n;j++)

            c.arr[i][j]=(a.arr[i][j]+b.arr[i][j])%mod;

    return c;

}

Matrix solve(int x){

    if(x==)

        return init;

    Matrix res=solve(x/),cur;

    if(x&){

        cur=Pow(init,unit,x/+);

        res=Add(res,Mul(cur,res));

        res=Add(res,cur);

    }else{

        cur=Pow(init,unit,x/);

        res=Add(res,Mul(cur,res));

    }

    return res;

}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d%d",&n,&k,&mod)){

        for(int i=;i<n;i++)

            for(int j=;j<n;j++){

                scanf("%d",&init.arr[i][j]);

                unit.arr[i][j]=(i==j?:);

            }

        Matrix res=solve(k);

        for(int i=;i<n;i++){

            for(int j=;j<n-;j++)

                printf("%d ",res.arr[i][j]);

            printf("%d\n",res.arr[i][n-]);

        }

    }

    return ;

}

巴特西

POJ 3233 Matrix Power Series （矩阵乘法）

最新文章

热门文章