线性基
导入
线性基,顾名思义,就是一个包含数字最少的集合,使得原集合中的任何数都能用线性基中的元素表示。
集合中的元素满足一些性质:
- 原集合中的任意元素都可以用线性基中的若干元素的异或和表示
- 线性基中任意数异或和不为 0 0 0,否则不满足集合大小最小
- 以任意顺序枚举原集合中元素,所得集合大小相同
- 大小为 n n n 的线性基可以表示 2 n 2^n 2n 个数;若线性基中存在二进制第 i i i 位为 1 1 1 的数,则可以表示 2 n − 1 2^{n-1} 2n−1 个二进制下第 i i i 位为 1 1 1 的数。
操作
插入
我们用数组 p
表示线性基,假设要插入
x
x
x,从高到低枚举
x
x
x 的二进制的每一位数字,如果
x
x
x 的第
i
i
i 位为
1
1
1 且
p
i
=
0
p_i=0
pi=0,那么令
p
i
=
x
p_i=x
pi=x 并结束插入;否则,令 x^=p[i]
,继续枚举下一位。
void insert(int x)
{
for(int i=50;i>=0;--i)
if(x>>i&1)
{
if(!p[i]) {p[i]=x;break;}
else x^=p[i];
}
}
求异或最大值
求原集合的子集的异或最大值,利用贪心思想。若 ans^p[i]>ans
,则 ans^=p[i]
。
int pmax()
{
int ans=0;
for(int i=50;i>=0;--i)
if((ans^p[i])>ans) ans^=p[i];
return ans;
}
求异或最小值
分两种情况考虑:
- 线性基大小 < < < 原集合大小:原集合中一定存在异或和为 0 0 0 的一些数,所以异或最小值为 0 0 0。
- 线性基大小 = = = 原集合大小:在线性基内求异或最小值,线性基内的最小元素与其他元素异或得到的值一定更大,所以异或最小值为线性基中最小元素。
剩的异或 k k k 小值先咕了 QwQ
本来学线性基是想过 YbtOJ 的最大异或对的,结果发现线性基是任意数的最大异或和,这一道题是一对,只能用 trie 树
练手板子题
代码如下:
#include <bits/stdc++.h>
using namespace std;
#define int long long
int p[55];
void insert(int x)
{
for(int i=50;i>=0;--i)
if(x>>i&1)
{
if(!p[i]) {p[i]=x;break;}
else x^=p[i];
}
}
int pmax()
{
int ans=0;
for(int i=50;i>=0;--i)
if((ans^p[i])>ans) ans^=p[i];
return ans;
}
signed main()
{
int n,x;cin>>n;
for(int i=1;i<=n;i++) cin>>x,insert(x);
cout<<pmax();
return 0;
}
行列式
行列式,是一种对于矩阵的特殊形式——方阵的表示形式。所谓方阵,就是 n × n n\times n n×n的矩阵。
一个
n
×
n
n\times n
n×n 的方阵
A
A
A 的行列式记为
det
(
A
)
\det(A)
det(A) 或者
∣
A
∣
|A|
∣A∣,一个
2
×
2
2\times2
2×2 矩阵的行列式可表示如下:
det
(
a
b
c
d
)
=
a
d
−
b
c
\det \begin{pmatrix} a&b\\ c&d \end{pmatrix}=ad-bc
det(acbd)=ad−bc
把一个
n
n
n 阶行列式中的元素
a
i
j
a_{ij}
aij 所在的第
i
i
i行和第
j
j
j列划去后,留下来的
n
−
1
n-1
n−1 阶行列式叫做元素
a
i
j
a_{ij}
aij 的余子式,记作
M
i
j
M_{ij}
Mij。记
A
i
j
=
(
−
1
)
i
+
j
M
i
j
A_{ij}=(-1)^{i+j}M_{ij}
Aij=(−1)i+jMij,叫做元素
a
i
j
a_{ij}
aij 的代数余子式。
一个
n
×
n
n\times n
n×n 矩阵的行列式等于其任意行(或列)的元素与对应的代数余子式乘积之和,即:
det
(
A
)
=
a
i
1
A
i
1
+
⋯
+
a
i
n
+
A
i
n
=
∑
j
=
1
n
a
i
j
(
−
1
)
i
+
j
det
(
A
i
j
)
\det(A)=a_{i1}A_{i1}+\cdots+a_{in}+A_{in}=\sum_{j=1}^na_{ij}(-1)^{i+j}\det(A_{ij})
det(A)=ai1Ai1+⋯+ain+Ain=j=1∑naij(−1)i+jdet(Aij)
代码实现:
int dett(int a[maxn][maxn],int n)//n为阶数
{
int dett=0,k=0,h=0;
if(n==1) return a[0][0];
else if(n==2) return a[0][0]*a[1][1]-a[0][1]*a[1][0];
else
{
for(int p=0;p<n;p++)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(j==p) continue;
tmp[h][k]=a[i][j],k++;
if(k==n-1) h++,k=0;
}
dett=dett+a[0][p]*pow(-1,p)*det(tmp,n-1)
}
return dett;
}
}
高斯消元
前置芝士
三角矩阵
上三角矩阵的对角线左下方的系数全部为 0 0 0,下三角矩阵的对角线右上方的系数全部为 0 0 0。三角矩阵可以看作是一般方阵的一种简化情形。由于带三角矩阵的矩阵方程容易求解,在解多元线性方程组时,总是将其系数矩阵通过初等变换化为三角矩阵来求解。
举个栗子,下面的矩阵
U
U
U 就是一个上三角矩阵。
U
=
[
u
1
,
1
u
1
,
2
u
1
,
3
⋯
u
1
,
n
0
u
2
,
2
u
2
,
3
⋯
u
2
,
n
0
0
⋱
⋱
⋮
⋮
⋮
0
⋱
u
n
−
1
,
n
0
0
⋯
0
u
n
,
n
]
U= \begin{bmatrix} u_{1,1}&u_{1,2}&u_{1,3}&\cdots&u_{1,n}\\ 0&u_{2,2}&u_{2,3}&\cdots&u_{2,n}\\ 0&0&\ddots&\ddots&\vdots\\ \vdots&\vdots&0&\ddots&u_{n-1,n}\\ 0&0&\cdots&0&u_{n,n} \end{bmatrix}
U=
u1,100⋮0u1,2u2,20⋮0u1,3u2,3⋱0⋯⋯⋯⋱⋱0u1,nu2,n⋮un−1,nun,n
增广矩阵
又称扩增矩阵,就是在系数矩阵的右边添上一列,这一列是线性方程组的等号右边的值。
高斯消元
基本思想
通过一系列的加减消元运算,将方程组化为上三角矩阵。然后再逐一回代求出 x x x。文章来源:https://www.toymoban.com/news/detail-737640.html
实现过程
解方程:
{
3
x
1
+
2
x
2
+
x
3
=
6
2
x
1
+
2
x
2
+
2
x
3
=
4
4
x
1
−
2
x
2
−
2
x
3
=
2
\begin{cases} 3x_1+2x_2+x_3=6\\ 2x_1+2x_2+2x_3=4\\ 4x_1-2x_2-2x_3=2 \end{cases}
⎩
⎨
⎧3x1+2x2+x3=62x1+2x2+2x3=44x1−2x2−2x3=2
我们把这个方程组写成增广矩阵的形式:文章来源地址https://www.toymoban.com/news/detail-737640.html
到了这里,关于线性代数相关笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!