矩阵
高斯消元
没啥好说的，直接上代码：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
double a[105][105];
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n+1;j++)
cin >> a[i][j];
for(int i = 1;i <= n;i++)
{
int ma = i;
for(int j = i+1;j <= n;j++)
if(fabs(a[j][i]) > fabs(a[ma][i]))ma = j;
for(int j = 1;j <= n+1;j++)swap(a[i][j],a[ma][j]);
if(!a[i][i]){cout << "No Solution";return 0;}
for(int j = 1;j <= n;j++)
if(i != j)
for(int k = i+1;k <= n+1;++k)
a[j][k] -= a[i][k]*(a[j][i]/a[i][i]);
}
for(int i = 1;i <= n;i++)
printf("%.2lf\n",a[i][n+1]/a[i][i]);
return 0;
}
行列式求值
定义：
\(det(A)=\mid A\mid =\sum\limits_p(-1)^{\tau(p)}\mathop{\Pi}\limits_{i=1}^na_{i,p_i}\)
其中 \(p\) 表示一个排列，\(\tau(p)\) 表示排列中逆序对的个数，即排列的奇偶性。
行列式的一些性质（感性理解即可）：
- 交换矩阵的两行，行列式取反；
- 交换矩阵 \(1\) 行于 \(1\) 列，行列式不变；
- 如果矩阵 \(A\) 中有一行（列），矩阵 \(B,C\) 中分别对应的 \(2\) 行（列）的元素之和，那么 \(\det(A)=\det(B)+\det(C)\)；
- 如果矩阵 \(A\) 两行成比例，则 \(det(A)=0\)；
- 把一个矩阵一行（列）的值全部乘一个常数加到另一行（列）上，行列式值不变。
行列式求值
根据以上性质，可以类似高斯消元将矩阵消成上三角矩阵，但是这里有模数，必须辗转消除来消元。
代码：
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int N = 605;
int n,mod;
ll a[N][N];
ll solve()
{
bool w = 1;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
{
if(i==j)continue;
while(a[i][i])
{
int now = a[j][i]/a[i][i];
for(int k = i;k <= n;k++)
a[j][k] = (a[j][k]-now*a[i][k]%mod+mod)%mod;
swap(a[i],a[j]);w = !w;
}
swap(a[i],a[j]);w = !w;
}
ll ans = 1;
for(int i = 1;i <= n;i++)(ans *= a[i][i]) %= mod;
return (w?ans:-ans);
}
inline int rd()
{
char c;int f = 1;
while((c = getchar())<'0'\mid \mid c>'9')if(c=='-')f = -1;
int x = c-'0';
while(('0' <= (c = getchar()))&&c <= '9')x = x*10+(c^48);
return x*f;
}
int main()
{
n = rd();mod = rd();
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
a[i][j] = rd();
cout << (solve()+mod)%mod;
return 0;
}
矩阵求逆
定义：
设 \(A\) 是一个方阵，如果存在一个矩阵 \(A^{-1}\) 使得 \(AA^{-1}=I\) 且 \(A^{-1}A=I\)，那么矩阵 \(A\) 就是可逆的，\(A^{-1}\) 就是 \(A\) 的逆矩阵。
高斯-约旦消元
高斯-约旦消元与高斯消元的区别在于：高斯-约旦消元是消成对角矩阵，而普通高斯消元是消成上三角矩阵。
高斯-约旦消元：
void Gauss_jordan(){
/***** 行的交换&加减消元 *****/
for(re int i=1,r;i<=n;++i){ //正在处理第i行
r=i;
for(re int j=i+1;j<=n;++j)
if(fabs(a[j][i])>fabs(a[r][i])) r=j;
if(fabs(a[r][i])<eps){
puts("No Solution");return;
}
if(i!=r) swap(a[i],a[r]);
for(re int k=1;k<=n;++k){
//每一行都处理
if(k==i) continue;
double p=a[k][i]/a[i][i];
for(re int j=i;j<=n+1;++j) a[k][j]-=p*a[i][j];
}
}
//上述操作后会剩下对角矩阵,答案要除以系数
for(re int i=1;i<=n;++i) printf("%.2lf\n",a[i][n+1]/a[i][i]);
}
矩阵求逆
思路：
- 将 \(A\) 和 \(I\) 放在一个矩阵中
- 将 \(A\) 消元成单位矩阵
- 此时原来的 \(I\) 变为 \(A\) 的逆矩阵
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int N = 405,mod = 1e9+7;
int n;
ll a[N][N << 1];
ll qp(ll x,int y)
{
ll ans = 1;
for(;y;y >>= 1,x = x*x%mod)
if(y&1)(ans *= x) %= mod;
return ans;
}
void solve()
{
for(int i = 1;i <= n;i++)
{
int r = i;
for(int j = i+1;j <= n;j++)
if(a[j][i] > a[r][i])r = j;
if(r != i)swap(a[i],a[r]);
if(!a[i][i]){puts("No Solution");return ;}
ll now = qp(a[i][i],mod-2);
for(int j = 1;j <= n;j++)
{
if(i==j)continue;
ll p = now*a[j][i]%mod;
for(int k = i;k <= n*2;k++)
a[j][k] = (a[j][k]-p*a[i][k]%mod+mod)%mod;
}
for(int j = 1;j <= n*2;j++)(a[i][j] *= now) %= mod;
}
for(int i = 1;i <= n;i++)
for(int j = n+1;j <= n*2;j++)
printf("%lld%c",a[i][j],j==n*2?'\n':' ');
}
inline int rd()
{
char c;int f = 1;
while((c = getchar())<'0'\mid \mid c>'9')if(c=='-')f = -1;
int x = c-'0';
while(('0' <= (c = getchar()))&&c <= '9')x = x*10+(c^48);
return x*f;
}
int main()
{
n = rd();
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
a[i][j] = rd(),a[i][n+i] = 1;
solve();
return 0;
}