矩阵十点【两】 poj 1575 Tr A poj 3233 Matrix Power Series

时间:2022-02-18 13:36:30

poj 1575  Tr A

主题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1575

题目大意:A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。

数据的第一行是一个T,表示有T组数据。

每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每一个数据的范围是[0,9]。表示方阵A的内容。

一个矩阵高速幂的裸题。

题解:

#include<iostream>
#include<stdio.h>
#include<cstring>
#define Mod 9973
using namespace std;
const int MAX = 11; struct Matrix
{
int v[MAX][MAX];
}; int n, k, M; Matrix mtMul(Matrix A, Matrix B) // 求矩阵 A * B
{
int i, j, k;
Matrix C;
for(i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
{
C.v[i][j] = 0;
for(k = 0; k < n; k ++)
C.v[i][j] = (A.v[i][k] * B.v[k][j] + C.v[i][j]) % Mod;
}
return C;
} Matrix mtPow(Matrix A, int k) // 求矩阵 A ^ k
{
if(k == 0)
{
memset(A.v, 0, sizeof(A.v));
for(int i = 0; i < n; i ++)
A.v[i][i] = 1;
return A;
} if(k == 1) return A; Matrix C = mtPow(A, k / 2);
if(k % 2 == 0)
return mtMul(C, C);
else
return mtMul(mtMul(C, C), A);
} int solv (Matrix A)
{
int ans=0;
for(int i=0;i<n;i++)
ans+=A.v[i][i]%Mod;
return ans;
} void out(Matrix A)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%d ",A.v[i][j]);
cout<<endl;
}
} int main ()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
Matrix A;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&A.v[i][j]);
Matrix ans;
ans=mtPow(A,k);
//out(ans);
cout<<solv(ans)%Mod<<endl;
}
}

poj 3233 Matrix Power Series

相同的矩阵高速幂裸题,主要是要用到
S(6) = (1 + A^3) * S(3)以及S(7) = A + (A + A^4) * S(3),这两个最后求的时候递归会省非常多时间
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
const int MAX = 32; struct Matrix
{
int v[MAX][MAX];
}; int n, k, M; Matrix mtAdd(Matrix A, Matrix B) // 求矩阵 A + B
{
int i, j;
Matrix C;
for(i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
C.v[i][j]=(A.v[i][j]+B.v[i][j])% M;
return C;
} Matrix mtMul(Matrix A, Matrix B) // 求矩阵 A * B
{
int i, j, k;
Matrix C;
for(i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
{
C.v[i][j] = 0;
for(k = 0; k < n; k ++)
C.v[i][j] = (A.v[i][k] * B.v[k][j] + C.v[i][j]) % M;
}
return C;
} Matrix mtPow(Matrix A, int k) // 求矩阵 A ^ k
{
if(k == 0)
{
memset(A.v, 0, sizeof(A.v));
for(int i = 0; i < n; i ++)
A.v[i][i] = 1;
return A;
} if(k == 1) return A; Matrix C = mtPow(A, k / 2);
if(k % 2 == 0)
return mtMul(C, C);
else
return mtMul(mtMul(C, C), A);
} Matrix mtCal(Matrix A, int k) // 求S (k) = A + A2 + A3 + … + Ak
{
if(k == 1) return A;
Matrix B = mtPow(A, (k+1) / 2);
Matrix C = mtCal(A, k / 2);
if(k % 2 == 0)
return mtMul(mtAdd(mtPow(A, 0), B), C); // 如S(6) = (1 + A^3) * S(3)。 else
return mtAdd(A, mtMul(mtAdd(A, B), C)); // 如S(7) = A + (A + A^4) * S(3)
} void out(Matrix A)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
cout<<A.v[i][j]<<" ";
cout<<A.v[i][n-1]<<endl;
}
} int main ()
{
Matrix A;
scanf("%d%d%d",&n,&k,&M);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&A.v[i][j]);
Matrix C=mtCal(A,k);
out(C); }


版权声明:本文博主原创文章,博客,未经同意不得转载。