nyoj_299_Matrix Power Series_矩阵快速幂

Matrix Power Series

时间限制: 1000 ms  |  内存限制:65535 KB
难度: 4
 
<dl class="problem&#45;display"> <dt> 描述 </dt> <dd> Given a  n ×  n matrix  A and a positive integer  k, find the sum  S =  A +  A 2 +  A 3 + … +  Ak. </dd> </dl>
 
<dl class="others"> <dt> 输入 </dt> <dd> The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10^9) and m (m < 10^4). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order. </dd> <dt> 输出 </dt> <dd> Output the elements of S modulo m in the same way as A is given. </dd> <dt> 样例输入 </dt> <dd>
2 2 4
0 1
1 1
</dd> <dt> 样例输出 </dt> <dd>
1 2
2 3
</dd> <dt> 来源 </dt> <dd> POJ Monthly </dd> <dt> 上传者 </dt> <dd> 张云聪 </dd> </dl>
#include <iostream>
#include <cstdio>

using namespace std;

int M=1000007;

struct Matrix{
    long int line,column;
    long int m[40][40];
};
struct Matr{
    long int line,column;
    long int m[70][70];
    Matr(Matrix x){
        line =x.line*2;
        column=x.column*2;
        for(int i=0;i<x.line*2;i++){
            for(int j=0;j<x.column;j++){
                m[i][j]=x.m[i%x.line][j];
            }
        }
        for(int i=0;i<x.line;i++){
            for(int j=x.column;j<x.column*2;j++){
                m[i][j]=0;
            }
        }
        for(int i=x.line;i<x.line*2;i++){
            for(int j=x.column;j<x.column*2;j++){
                if(i==j){
                    m[i][j]=1;
                }else{
                    m[i][j]=0;
                }
            }
        }
    }
};

Matr mult(Matr a,Matr b){
    Matr ans(a);
    ans.line=a.line;
    ans.column=b.column;
    //ans=inist(ans,0);
    for(int i=0;i<ans.line;i++){
        for(int j=0;j<ans.column;j++){
            ans.m[i][j]=0;
            for(int k=0;k<ans.column;k++){
                ans.m[i][j]+=(a.m[i][k]*b.m[k][j]);
                ans.m[i][j]%=M;
            }
        }
    }
    return ans;
}

Matr fast_matrix(Matr x,int n){
    Matr an(x),tmp(x);
    for(int i=0;i<x.line;i++){
        for(int j=0;j<x.column;j++){
            an.m[i][j]=x.m[i+x.line/2][j];
        }
    }
    an.line/=2;
    while(n){
        if(n%2!=0){
            an=mult(an,tmp);
        }
        tmp=mult(tmp,tmp);
        n>>=1;
    }
    return an;
}

int main()
{
    int n,m,k;
    Matrix a;
    scanf("%d %d %d",&n,&k,&m);
    M=m;
    a.line=n;
    a.column=n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a.m[i][j]);
        }
    }
    Matr ans(a);
    Matr ans2=fast_matrix(ans,k-1);
    for(int i=0;i<ans2.line;i++){
        for(int j=0;j<ans2.column/2;j++){
            printf("%d ",ans2.m[i][j]);
        }
        printf("\n");
    }
    return 0;
}

 

全部评论

相关推荐

Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
06-20 19:40
中原工学院 Java
网络存储:十几天不会让你拉人办卡就结束了吧?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务