线性代数入门
矩阵
运算法则
加法
两个矩阵 \(A\) 和 \(B\) 相加，要求它们的维度相同。结果矩阵
\(C=A+B\) 的每个元素是 \(A\) 和 \(B\) 对应元素的和。\(C_{i,j}=A_{i,j}+B_{i,j}\) ##### 数乘 矩阵
\(A\) 与标量 \(k\) 相乘，结果矩阵 \(B=kA\) 的每个元素是 \(A\) 的对应元素乘以 \(k\)。\(B_{i,j}=k\cdot A_{i,j}\) ##### 乘法 矩阵
\(A\) 与矩阵 \(B\) 相乘，要求 \(A\) 的列数等于 \(B\) 的行数。结果矩阵 \(C=AB\) 的每个元素是 \(A\) 的行向量与 \(B\) 的列向量的点积。\(C_{i,j}=\sum_{k=1}^nA_{i,k}\cdot B_{k,j}\)
注意：矩阵乘法不满足交换律 #### 矩阵快速幂
其实和普通快速幂几乎一样。 我们要使用单位矩阵 \[I=\begin{bmatrix}
1&0&\cdots&0\\
0&1&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&1
\end{bmatrix}\]
作为初始矩阵。因为它乘任何矩阵还得跟它乘的那个矩阵，类似于 \(1\) 在普通快速幂中的作用。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int n,k;
struct matrix{
int a[110][110];
matrix(){
memset(a,0,sizeof(a));
}
matrix operator*(const matrix &b)const{
matrix res;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
return res;
}
}ans,base,a;
void init(){
for(int i=1;i<=n;i++)
base.a[i][i]=1;
return;
}
matrix qpow(matrix a,long long b){
matrix res=base;
while(b){
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
signed main(){
scanf("%lld%lld",&n,&k);
init();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&a.a[i][j]);
ans=qpow(a,k);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
printf("%lld ",ans.a[i][j]);
printf("\n");
}
return 0;
}
高斯消元
现有线性方程组 \[\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1\\
a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\
\cdots\\
a_{n,1}x_1+a_{n,2}x_2+\cdots+a_{n,n}x_n=b_n
\end{cases}\] 求解该方程组。 为了方便起见，我们用矩阵表示方程组：
\[\left[\begin{matrix}a_{1,1}&a_{1,2}&a_{1,3}&\cdots&a_{1,n}\\
a_{2,1}&a_{2,2}&a_{2,3}&\cdots&a_{2,n}\\
a_{3,1}&a_{3,2}&a_{3,3}&\cdots&a_{3,n}\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
a_{n,1}&a_{n,2}&a_{n,3}&\cdots&a_{n,n}
\end{matrix}\middle|
\begin{matrix}
b_{1}\\
b_{2}\\
b_{3}\\
\vdots\\
b_{n}
\end{matrix}\right]\] 首先消去除 \(1\) 式以外所有式子中的 \(x_1\)，然后消去除 \(1\) 式和 \(2\) 式外所有式子中的 \(x_2\)……最后式子变为一个三角形的结构 \[\left[\begin{matrix}a_{1,1}'&a_{1,2}'&a_{1,3}'&\cdots&a_{1,n}'\\
0&a_{2,2}'&a_{2,3}'&\cdots&a_{2,n}'\\
0&0&a_{3,3}'&\cdots&a_{3,n}'\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&\cdots&a_{n,n}'
\end{matrix}\middle|
\begin{matrix}
b_{1}'\\
b_{2}'\\
b_{3}'\\
\vdots\\
b_{n}'
\end{matrix}\right]\] 之后再一点点代回求解，时间复杂度 \(O(n^3)\)。 对于无解的判断：某一行前 \(n\) 个数均为 \(0\)，最后的结果却不为 \(0\)。 对于无数解的判断：某一行 \(n+1\) 个数均为 \(0\)。 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26for(int i=1;i<=n;i++){
int r=i;
for(int j=i+1;j<=n;j++)
if(fabs(matrix[r][i])<fabs(matrix[j][i]))
r=j;//寻找主元
if(fabs(matrix[r][i])<eps){
printf("No Solution");//若主元为0，方程组无解或无穷多解
return 0;
}
if(i!=r)
swap(matrix[i],matrix[r]);
double div=matrix[i][i];
for(int j=i;j<=n+1;j++)
matrix[i][j]/=div;
for(int j=i+1;j<=n;j++){
div=matrix[j][i];
for(int k=i;k<=n+1;k++)
matrix[j][k]-=matrix[i][k]*div;
}//消元
}
ans[n]=matrix[n][n+1];
for(int i=n-1;i;i--){
ans[i]=matrix[i][n+1];
for(int j=i+1;j<=n;j++)
ans[i]-=matrix[i][j]*ans[j];
}//回代1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35for(int i=1;i<=n;i++){
int pivot=rank1+1;//rank1为矩阵的秩
for(int j=rank1+1;j<=n;j++)
if(fabs(matrix[pivot][i])<fabs(matrix[j][i]))
pivot=j;
if(fabs(matrix[pivot][i])<eps)
continue;//全为零
if(pivot!=rank1+1)
swap(matrix[pivot],matrix[rank1+1]);
double div=matrix[rank1+1][i];
for(int j=i;j<=n+1;j++)
matrix[rank1+1][j]/=div;
for(int j=1;j<=n;j++){
if(j==rank1+1||fabs(matrix[j][i])<eps)
continue;
div=matrix[j][i];
for(int k=i;k<=n+1;k++)
matrix[j][k]-=matrix[rank1+1][k]*div;
}//消元
rank1++;
}
for(int i=rank1+1;i<=n;i++)
if(fabs(matrix[i][n+1])>eps){
printf("-1");
return 0;//无解
}
if(rank1<n){
printf("0");
return 0;//无数解
}
for(int i=n;i;i--){
ans[i]=matrix[i][n+1];
for(int j=i+1;j<=n;j++)
ans[i]-=matrix[i][j]*ans[j];
}//回代1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17for(int i=1,line=1,cur;i<=n;i++){
cur=line;
for(int j=line+1;j<=n;j++)
if(fabs(a[j][i])>fabs(a[cur][i]))
cur=j;
if(fabs(a[cur][i])<eps) continue;
double temp=a[cur][i];
for(int j=1;j<=n+1;j++)
swap(a[cur][j],a[line][j]),a[line][j]/=temp;
for(int j=1;j<=n;j++)
if(j!=line){
temp=a[j][i];
for(int k=1;k<=n+1;k++)
a[j][k]-=a[line][k]*temp;
}
++line;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32struct LBase{
long long d[61];
LBase(){
memset(d,0,sizeof(d));
}
bool insert(long long x){
for(int i=60;i>=0;i--){
if(x&1ll<<i){
if(d[i])
x^=d[i];
else{
d[i]=x;
return 1;
}
}
}
return 0;
}
long long query_max(){
long long x=0;
for(int i=60;i>=0;i--)
if(d[i]&&(x^d[i])>x)
x^=d[i];
return x;
}
void merge(const LBase &a){
for(int i=60;i>=0;i--)
if(a.d[i])
insert(a.d[i]);
return;
}
};