poj3233(矩阵快速幂)

2017年02月24日 10点热度 0人点赞 0条评论
Matrix Power Series
Time Limit: 3000MS   Memory Limit: 131072K
Total Submissions: 21884   Accepted: 9165

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

#include
#include
#include
using namespace std;
long long n,k,m,ans[63][63];
void fun(long long nt)
{
    long long a[63][63],t[63][63];
    memcpy(a,ans,sizeof(a));
    while(nt)
    {
        if(nt&1)
        {
            memcpy(t,ans,sizeof(t));
            memset(ans,0,sizeof(ans));
            for(int i=1; i<=2*n; i++)
                for(int j=1; j<=2*n; j++)
                {
                    for(int k=1; k<=2*n; k++)
                        ans[i][j]+=t[i][k]*a[k][j];
                    ans[i][j]%=m;
                }

        }
        nt>>=1;
        memcpy(t,a,sizeof(t));
        memset(a,0,sizeof(a));
        for(int i=1; i<=2*n; i++)
            for(int j=1; j<=2*n; j++)
            {
                for(int k=1; k<=2*n; k++)
                    a[i][j]+=t[i][k]*t[k][j];
                a[i][j]%=m;
            }
    }
}
int main()
{
    while(~scanf("%lld%lld%lld",&n,&k,&m))
    {
        memset(ans,0,sizeof(ans));
        for(int i=1; i<=n; i++)
            ans[i][i]=1;
        for(int i=n+1; i<=2*n; i++)
            for(int j=1; j<=n; j++)
            {
                scanf("%lld",&ans[i][j]);
                ans[i][j+n]=ans[i][j];
            }
        fun(k-1);
        for(int i=n+1; i<=2*n; i++)
        {
            for(int j=1; j<=n; j++)
                printf("%lld ",ans[i][j]);
            printf("n");
        }
    }
    return 0;
}
未经允许不得转载!poj3233(矩阵快速幂)

update

纸上得来终觉浅, 绝知此事须躬行。