• 欢迎光临~

# 1矩阵

## 1.3 矩阵快速幂

#### 1.1 1.2 1.3 归总代码如下：

``````struct Matrix
{
int n, m;
double a[MAXN][MAXN];

void clear()
{
n = m = 0;
memset(a, 0, sizeof(a));
}

void init(int t)
{
clear();
n = m = t;
for (int i = 1; i <= t; ++i)
a[i][i] = 1;
}
Matrix operator + (const Matrix &b) const
{
Matrix tmp;
tmp.n = n;
tmp.m = m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
tmp.a[i][j] = a[i][j] + b.a[i][j];
return tmp;
}

Matrix operator - (const Matrix &b) const
{
Matrix tmp;
tmp.n = n;
tmp.m = m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
tmp.a[i][j] = a[i][j] - b.a[i][j];
return tmp;
}

Matrix operator * (const Matrix &b) const
{
Matrix tmp;
tmp.clear();
tmp.n = n;
tmp.m = b.m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= b.m; ++j)
for (int k = 1; k <= m; ++k)
tmp.a[i][j] += a[i][k] * b.a[k][j];
return tmp;
}

void gauss()
{
for (int i = 1; i <= n; ++i)
{
for (int j = i; j <= n; ++j)
if (fabs(a[j][i]) > eps)
{
if (j == i)
break;
for (int k = i; k <= m; ++k)
swap(a[i][k], a[j][k]);
break;
}
for (int j = m; j >= i; --j)
a[i][j] /= a[i][i];
for (int j = 1; j <= n; ++j)
{
if (j == i || fabs(a[j][i]) < eps)
continue;
double tmp = a[j][i] / a[i][i];
for (int k = i; k <= m; ++k)
a[j][k] -= tmp * a[i][k];
}
}
}

Matrix pow(int t)
{
Matrix res;
res.init(n);
Matrix tmp = *this;
while (t)
{
if (t & 1)
{
res = res * tmp;
}
tmp = tmp * tmp;
t >>= 1;
}
return res;
}

void print()
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
cout << a[i][j] << ' ';
cout << endl;
}
}
};

``````

## 1.4 矩阵求逆

``````void matrix_inv(Matrix a)
{
int n = a.n;
b.n = b.m = n;
a.gauss();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
b.a[i][j] = a.a[i][j + n];
}
``````