📄 矩阵乘方和.cpp
字号:
/*描述
给出一个n*n的矩阵和正整数k,请求出S=A+A^2+A^3+A^4+...+A^k的值.A^x表示x个A相乘的结果.
关于输入
输入包含一组数据.
第一行是三个正整数n k m, (n<=30,k<=1000000000,m<=10000).
接下来n行,每行n个数,表示这个矩阵.
关于输出
输出矩阵S对m取模后的值,包括n行,每行n个数
例子输入
2 2 4
0 1
1 1
例子输出
1 2
2 3
*/
#include<iostream>
#include<string.h>
#define size 31
using namespace std;
int main()
{
int n,k,m;
cin>>n>>k>>m;
int num;
int(*M)[size]=new int[n][size];
int (*Sum)[size]=new int [n][size];
int i=0,j=0,h=0,s=0;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
cin>>num;
Sum[i][j]=0;M[i][j]=0;
Sum[i][j]=M[i][j]=num%m;
}
}
if(k==1){
for(i=0;i<n;i++){
for(j=0;j<n-1;j++)
cout<<Sum[i][j]<<' ';
cout<<Sum[i][n-1]<<endl;
}
return 0;
}
for(s=1;s<k;s++){
for(i=0;i<n;i++){
Sum[i][i]++;
}
int (*NewM)[size]=new int [n][size];
for(i=0;i<n;i++){
for(j=0;j<n;j++){
NewM[i][j]=0;
for(h=0;h<n;h++){
NewM[i][j]+=Sum[i][h]*M[h][j];
//cout<<M[i][j]<<'*'<<endl;
}
NewM[i][j]=NewM[i][j]%m;
//cout<<NewM[i][j]<<endl;
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++){
Sum[i][j]=NewM[i][j];
//cout<<Sum[i][j]<<'&'<<endl;
}
}
for(i=0;i<n;i++){
for(j=0;j<n-1;j++)
cout<<Sum[i][j]<<' ';
cout<<Sum[i][n-1]<<endl;
}
return 0;
}
/*
4 4 3
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
*/
//void Add(int *M[],int n)
//{
// int i=0,j=0;
// for(i=0;i<n;i++)
// for(j=0;j<n;j++)
// M[i][j]++;
//}
//long int *Multiply(long int *A[],long int *B[],int n)
//{
// int i=0,j=0,h=0;
// long int (*M)[size]=new long int [n][size];
// for(i=0;i<n;i++){
// for(j=0;j<n;j++){
// for(h=0;h<n;h++)
// M[i][j]+=A[i][h]*B[h][j];
// M[i][j]=M[i][j]%m;
//
//
// }
// }
// return M;
//}
/*
#include<iostream>
#include<string.h>
using namespace std;
void FuZhi(int **A,int Ax0,int Ax1,int Ay0,int Ay1,int **B,int Bx0,int By0){
int i=0,j=0;
for(i=0;i<Ax1-Ax0;i++)
for(j=0;j<Ay1-Ay0;j++)
A[Ax0+i][Ay0+j]=B[Bx0+i][By0+j];
}
int **Add(int **A,int **B,int x,int y){
int i=0,j=0;
int **NewMat;
NewMat=new (int *) [x];
for(i=0;i<x;i++){
NewMat[i]=new int [y];
NewMat[i][j]=A[i][j]+B[i][j];
}
return NewMat;
}
int **Matrix(int **A,int Ax,int Ay,int **B,int Bx,int By){
int i=0,j=0,h=0;
if(Ax<=2&&By<=2){
int **NewMat=new (int *) [Ax];
for(i=0;i<Ax;i++){
NewMat[i]=new int [By];
for(j=0;j<By;j++) NewMat[i][j]=0;
}
for(i=0;i<By;i++)
for(j=0;j<Ax;j++)
for(h=0;h<Ay;h++)
NewMat[i][j]+=A[i][h]*B[h][j];
return NewMat;
}
int Ax_1=Ax/2;
int Ax_2=Ax-Ax/2;
int Ay_1=Ay/2;
int Ay_2=Ay-Ay/2;
int Bx_1=Bx/2;
int Bx_2=Bx-Bx/2;
int By_1=By/2;
int By_2=By-By/2;
//****************** Matrix A **************************
//MatrixA_11
int **MarA_11=new (int *) [Ax_1];
for(i=0;i<Ax_1;i++){
MarA_11[i]=new int [Ay_1];
for(j=0;j<Ay_1;j++) MarA_11[i][j]=0;
}
//MatrixA_21
int **MarA_21=new (int *) [Ax_2];
for(i=0;i<Ax_2;i++){
MarA_21[i]=new int [Ay_1];
for(j=0;j<Ay_1;j++) MarA_21[i][j]=0;
}
//MatrixA_12
int **MarA_12=new (int *) [Ax_1];
for(i=0;i<Ax_1;i++){
MarA_12[i]=new int [Ay_2];
for(j=0;j<Ay_2;j++) MarA_12[i][j]=0;
}
//MatrixA_22
int **MarA_22=new (int *) [Ax_2];
for(i=0;i<Ax_2;i++){
MarA_22[i]=new int [Ay_2];
for(j=0;j<Ay_2;j++) MarA_22[i][j]=0;
}
//********************************************************
//******************** Matrix B **************************
//MatrixB_11
int **MarB_11=new (int *) [Bx_1];
for(i=0;i<Bx_1;i++){
MarB_11[i]=new int [By_1];
for(j=0;j<By_1;j++) MarB_11[i][j]=0;
}
//MatrixB_21
int **MarB_21=new (int *) [Bx_1];
for(i=0;i<Bx_2;i++){
MarB_21[i]=new int [By_1];
for(j=0;j<By_1;j++) MarB_21[i][j]=0;
}
//MatrixB_12
int **MarB_12=new (int *) [Bx_1];
for(i=0;i<Bx_1;i++){
MarB_12[i]=new int [By_2];
for(j=0;j<By_2;j++) MarB_12[i][j]=0;
}
//MatrixB_22
int **MarB_22=new (int *) [Bx_2];
for(i=0;i<Bx_2;i++){
MarB_22[i]=new int [By_2];
for(j=0;j<By_2;j++) MarB_22[i][j]=0;
}
//********************************************************
//******************** Matrix C **************************
//MatrixC[Ax][By]
int **MarC=new (int *) [Ax];
for(i=0;i<Ax;i++){
MarC[i]=new int [By];
for(j=0;j<By;j++) MarC[i][j]=0;
}
//MatrixC_11
int **MarC_11=new (int *) [Ax_1];
for(i=0;i<Ax_1;i++){
MarC_11[i]=new int [By_1];
for(j=0;j<By_1;j++) MarB_11[i][j]=0;
}
//MatrixC_21
int **MarC_21=new (int *) [Ax_2];
for(i=0;i<Ax_2;i++){
MarC_21[i]=new int [By_1];
for(j=0;j<By_1;j++) MarB_21[i][j]=0;
}
//MatrixC_12
int **MarC_12=new (int *) [Ax_1];
for(i=0;i<Ax_1;i++){
MarC_12[i]=new int [By_2];
for(j=0;j<By_2;j++) MarC_12[i][j]=0;
}
//MatrixC_22
int **MarC_22=new (int *) [Ax_2];
for(i=0;i<Ax_2;i++){
MarC_22[i]=new int [By_2];
for(j=0;j<By_2;j++) MarB_22[i][j]=0;
}
//*******************************************************
FuZhi(MarA_11,0,Ax_1,0,Ay_1,A,0,0);
FuZhi(MarA_21,0,Ax_2,0,Ay_1,A,Ax_1,0);
FuZhi(MarA_12,0,Ax_1,0,Ay_2,A,0,Ay_1);
FuZhi(MarA_22,0,Ax_2,0,Ay_2,A,Ax_1,Ay_1);
FuZhi(MarB_11,0,Bx_1,0,By_1,B,0,0);
FuZhi(MarB_21,0,Bx_2,0,By_1,B,Bx_1,0);
FuZhi(MarB_12,0,Bx_1,0,By_2,B,0,By_1);
FuZhi(MarB_22,0,Bx_2,0,By_2,B,Bx_1,By_1);
//Matrix A_11*B_11
int **MarA11_B11=new (int *) [Ax_1];
for(i=0;i<Ax_1;i++){
MarA11_B11[i]=new int [By_1];
for(j=0;j<By_1;j++) MarA11_B11[i][j]=0;
}
MarA11_B11=Matrix(MarA_11,Ax_1,Ay_1,MarB_11,Bx_1,By_1);
//Matrix A_12*B_21
int **MarA12_B21=new (int *) [Ax_1];
for(i=0;i<Ax_1;i++){
MarA12_B21[i]=new int [By_1];
for(j=0;j<By_1;j++) MarA12_B21[i][j]=0;
}
MarA12_B21=Matrix(MarA_12,Ax_1,Ay_2,MarB_21,Bx_2,By_1);
MarC_11=Add(MarA11_B11,MarA12_B21,Ax_1,By_1);
//Matrix A_21*B_11
int **MarA21_B11=new (int *) [Ax_2];
for(i=0;i<Ax_2;i++){
MarA21_B11[i]=new int [By_1];
for(j=0;j<By_1;j++) MarA21_B11[i][j]=0;
}
MarA21_B11=Matrix(MarA_21,Ax_2,Ay_1,MarB_11,Bx_1,By_1);
//Matrix A_22*B_21
int **MarA22_B21=new (int *) [Ax_2];
for(i=0;i<Ax_2;i++){
MarA22_B21[i]=new int [By_1];
for(j=0;j<By_1;j++) MarA22_B21[i][j]=0;
}
MarA22_B21=Matrix(MarA_22,Ax_2,Ay_2,MarB_21,Bx_2,By_1);
MarC_21=Add(MarA21-B11,MarA22_B21,Ax_2,By_1);
//Matrix A_11*B_12
int **MarA11_B12=new (int *) [Ax_1];
for(i=0;i<Ax_1;i++){
MarA11_B12[i]=new int [By_2];
for(j=0;j<By_2;j++) MarA11_B12[i][j]=0;
}
MarA11_B12=Matrix(MarA_11,Ax_1,Ay_1,MarB_12,Bx_1,By_2);
//Matrix A_12*B_22
int **MarA12_B22=new (int *) [Ax_1];
for(i=0;i<Ax_1;i++){
MarA12_B22[i]=new int [By_2];
for(j=0;j<By_2;j++) MarA12_B22[i][j]=0;
}
MarA12_B22=Matrix(MarA_12,Ax_1,Ay_2,MarB_22,Bx_2,By_2);
MarC_12=Add(MarA11_B12,MarA12_B22,Ax_1,By_2);
//Matrix A_21*B_12
int **MarA21_B12=new (int *) [Ax_2];
for(i=0;i<Ax_2;i++){
MarA21_B12[i]=new int [By_2];
for(j=0;j<By_2;j++) MarA21_B12[i][j]=0;
}
MarA21_B12=Matrix(MarA_21,Ax_2,Ay_1,MarB_12,Bx_1,By_2);
//Matrix A_22*B_22
int **MarA22_B22=new (int *) [Ax_2];
for(i=0;i<Ax_2;i++){
MarA22_B22[i]=new int [By_2];
for(j=0;j<By_2;j++) MarA22_B22[i][j]=0;
}
MarA22_B22=Matrix(MarA_22,Ax_2,Ay_2,MarB_22,Bx_2,By_2);
MarC_22=Add(MarA21_B12,MarA22_B22,Ax_2,By_2);
FuZhi(MarC,0,Ax_1,0,By_1,MarC_11,0,0);
FuZhi(MarC,Ax_1,Ax,0,By_1,MarC_21,0,0);
FuZhi(MarC,0,Ax_1,By_1,By,MarC_12,0,0);
FuZhi(MarC,Ax_1,Ax,By_1,By,MarC_22,0,0);
return MarC;
}
int main()
{
int n,k,m;
cin>>n>>k>>m;
return 0;
}
*/
//#include<iostream>
//#include<stack>
//#include<cmath>
//using namespace std;
//
//#define size 61
//
//int main()
//{
// int n,f,m;
// cin>>n>>f>>m;
// long int a[size][size]={0};
// long int b[size][size]={0};
// long int c[size][size]={0};
// int i,j,k;
// for(i=0;i<n;i++)
// for(j=0;j<n;j++) {
// cin>>a[i][j];
// c[i][j]=a[i][j];
// }
// stack<long int> astack;
// int mm=f+1;
// while(mm>1) {
// if(mm%2) {
// mm-=1;
// astack.push(1);
// }
// astack.push(2);
// mm/=2;
// }
// for(i=0;i<n;i++) {
// a[i][i+n]=1;
// c[i][i+n]=1;
// }
// for(i=n;i<2*n;i++) {
// a[i][i]=1;
// c[i][i]=1;
// }
// while(!astack.empty()) {
// for(i=0;i<2*n;i++)
// for(j=0;j<2*n;j++) {
// int pp=0;
// for(k=0;k<2*n;k++) {
// if(astack.top()==2)
// pp=(pp+c[i][k]*c[k][j])%m;
// else pp=(pp + c[i][k]*a[k][j])%m;
// }
// b[i][j]=pp;
// }
// for(i=0;i<2*n;i++)
// for(j=0;j<2*n;j++)
// c[i][j]=b[i][j];
// astack.pop();
// }
// for(i=0;i<n;i++)
// {
// c[i][i+n]-=1;
// if(c[i][i + n] == -1)c[i][i + n] += m;
// }
// for(i=0;i<n;i++) {
// for(j=n;j<2*n-1;j++)
// cout<<c[i][j]%m<<" ";
// cout<<c[i][j]%m<<endl;
// }
// return 0;
//}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -