ACM模版
矩阵乘法
#define MAXN 111
#define mod(x) ((x) % MOD)
#define MOD 1000000007
#define LL long long
int n;
struct mat
{
int m[MAXN][MAXN];
};
mat
operator * (mat a, mat &b)
{
mat ret;
memset(ret.m,
0,
sizeof(ret.m));
for (
int k =
0; k < n; k++)
{
for (
int i =
0; i < n; i++)
{
if (a.m[i][k])
{
for (
int j =
0; j < n; j++)
{
ret.m[i][j] = mod(ret.m[i][j] + (LL)a.m[i][k] * b.m[k][j]);
}
}
}
}
return ret;
}
矩阵乘法 + 判等
struct Matrix
{
Type mat[MAXN][MAXN];
int n, m;
Matrix()
{
n = m = MAXN;
memset(mat,
0,
sizeof(mat));
}
Matrix(
const Matrix &a)
{
set_size(a.n, a.m);
memcpy(mat, a.mat,
sizeof(a.mat));
}
Matrix &
operator = (
const Matrix &a)
{
set_size(a.n, a.m);
memcpy(mat, a.mat,
sizeof(a.mat));
return *
this;
}
void set_size(
int row,
int column)
{
n = row;
m = column;
}
friend Matrix
operator * (
const Matrix &a,
const Matrix &b)
{
Matrix ret;
ret.set_size(a.n, b.m);
for (
int i =
0; i < a.n; ++i)
{
for (
int k =
0; k < a.m; ++k)
{
if (a.mat[i][k])
{
for (
int j =
0; j < b.m; ++j)
{
if (b.mat[k][j])
{
ret.mat[i][j] = ret.mat[i][j] + a.mat[i][k] * b.mat[k][j];
}
}
}
}
}
return ret;
}
friend bool operator == (
const Matrix &a,
const Matrix &b)
{
if (a.n != b.n || a.m != b.m)
{
return false;
}
for (
int i =
0; i < a.n; ++i)
{
for (
int j =
0; j < a.m; ++j)
{
if (a.mat[i][j] != b.mat[i][j])
{
return false;
}
}
}
return true;
}
};
矩阵快速幂
#define MAXN 111
#define mod(x) ((x) % MOD)
#define MOD 1000000007
#define LL long long
int n;
struct mat
{
int m[MAXN][MAXN];
} unit;
mat
operator * (mat a, mat &b)
{
mat ret;
memset(ret.m,
0,
sizeof(ret.m));
for (
int k =
0; k < n; k++)
{
for (
int i =
0; i < n; i++)
{
if (a.m[i][k])
{
for (
int j =
0; j < n; j++)
{
ret.m[i][j] = mod(ret.m[i][j] + (LL)a.m[i][k] * b.m[k][j]);
}
}
}
}
return ret;
}
void init_unit()
{
for (
int i =
0; i < MAXN; i++)
{
unit.m[i][i] =
1;
}
return ;
}
mat pow_mat(mat a, LL n)
{
mat ret = unit;
while (n)
{
if (n &
1)
{
ret = ret * a;
}
n >>=
1;
a = a * a;
}
return ret;
}
int main()
{
LL x;
init_unit();
while (
cin >> n >> x)
{
mat a;
for (
int i =
0; i < n; i++)
{
for (
int j =
0; j < n; j++)
{
cin >> a.m[i][j];
}
}
a = pow_mat(a, x);
for (
int i =
0; i < n; i++)
{
for (
int j =
0; j < n; j++)
{
if (j +
1 == n)
{
cout << a.m[i][j] << endl;
}
else
{
cout << a.m[i][j] <<
" ";
}
}
}
}
return 0;
}
2017.6.13 修改矩阵乘法部分,优化,引用、判0
转载请注明原文地址: https://ju.6miu.com/read-1295834.html