【牛客】矩阵幂(C++)

【牛客】矩阵幂(C++)题目描述给定一个n*n的矩阵,求该矩阵的k次幂,即P^k。输入描述:第一行:两个整数n(2<=n<=10)、k(1<=k<=5),两个数字之间用一个空格隔开,含义如上所示。接下来有n行,每行n个正整数,其中,第i行第j个整数表示矩阵中第i行第j列的矩阵元素Pij且(0<=Pij<=10)。另外,数据保证最后结果不会超过10^8。输出描述:…

大家好,欢迎来到IT知识分享网。

题目描述

给定一个n*n的矩阵,求该矩阵的k次幂,即P^k。

输入描述:

 
第一行:两个整数n(2<=n<=10)、k(1<=k<=5),两个数字之间用一个空格隔开,含义如上所示。
接下来有n行,每行n个正整数,其中,第i行第j个整数表示矩阵中第i行第j列的矩阵元素Pij且(0<=Pij<=10)。另外,数据保证最后结果不会超过10^8。

输出描述:

对于每组测试数据,输出其结果。格式为:
n行n列个整数,每行数之间用空格隔开,注意,每行最后一个数后面不应该有多余的空格。

要注意矩阵结构体定义格式,掌握快速幂算法,打印矩阵的函数需要单独封装不然会报错,因为嵌套太多。

#include <iostream>
#include <cstdio>

using namespace std;

struct Matrix
{
    int matrix[10][10];
    int row,col;
    Matrix(int r,int c):row(r),col(c){}  //构造函数
};

Matrix Multiplication(Matrix m,Matrix n)  //矩阵乘法
{
    Matrix y(m.row,n.col);
    for(int i=0;i<m.row;i++)
    {
        for(int j=0;j<n.col;j++)
        {
            int sum=0;
            for(int k=0;k<m.col;k++)
            {
                sum+=(m.matrix[i][k]*n.matrix[k][j]);
            }
            y.matrix[i][j]=sum;
        }
    }
    return y;
}

Matrix Fastmodular(Matrix p,int k)   //快速幂运算
{
    Matrix x(p.row,p.col);
    for(int i=0;i<x.row;i++)   //初始单位矩阵
    {
        for(int j=0;j<x.col;j++)
        {
            if(i==j)
                x.matrix[i][j]=1;
            else
                x.matrix[i][j]=0;
        }
    }
    while(k)
    {
        if(k%2)
            x=Multiplication(x,p);
        k=k/2;
        p=Multiplication(p,p);
    }
    return x;
}

void printfmatrix(Matrix z)  //防止段错误
{
    for(int i=0;i<z.row;i++)
        {
            for(int j=0;j<z.col;j++)
            {
                if(j==(z.col-1))
                    printf("%d",z.matrix[i][j]);   //最后一个数字后面不应该有多余空格
                else
                    printf("%d ",z.matrix[i][j]);
            }
            printf("\n");
        }
    return ;
}

int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        Matrix p(n,n);
        for(int i=0;i<p.row;i++)       //接收p矩阵
        {
            for(int j=0;j<p.col;j++)
            {
                int x;
                scanf("%d",&x);
                p.matrix[i][j]=x;
            }
        }
        Matrix answer(n,n);
        answer=Fastmodular(p,k);
        printfmatrix(answer);
    }
    return 0;
}

提交结果:

【牛客】矩阵幂(C++)

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/12837.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信