线性代数相关笔记

线性基

导入

线性基，顾名思义，就是一个包含数字最少的集合，使得原集合中的任何数都能用线性基中的元素表示。

集合中的元素满足一些性质：

• 原集合中的任意元素都可以用线性基中的若干元素的异或和表示
• 线性基中任意数异或和不为 $0$，否则不满足集合大小最小
• 以任意顺序枚举原集合中元素，所得集合大小相同
• 大小为 $n$ 的线性基可以表示 $2^n$ 个数；若线性基中存在二进制第 $i$ 位为 $1$ 的数，则可以表示 $2^{n-1}$ 个二进制下第 $i$ 位为 $1$ 的数。

操作

插入

我们用数组 p 表示线性基，假设要插入 $x$，从高到低枚举 $x$ 的二进制的每一位数字，如果 $x$ 的第 $i$ 位为 $1$ 且 $p_i=0$，那么令 $p_i=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];
        }
}
1
2
3
4
5
6
7
8
9

求异或最大值

求原集合的子集的异或最大值，利用贪心思想。若 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;
}
1
2
3
4
5
6
7

求异或最小值

分两种情况考虑：

• 线性基大小 $<$ 原集合大小：原集合中一定存在异或和为 $0$ 的一些数，所以异或最小值为 $0$。
• 线性基大小 $=$ 原集合大小：在线性基内求异或最小值，线性基内的最小元素与其他元素异或得到的值一定更大，所以异或最小值为线性基中最小元素。

剩的异或 $k$ 小值先咕了 QwQ 本来学线性基是想过 YbtOJ 的最大异或对的，结果发现线性基是任意数的最大异或和，这一道题是一对，只能用 trie 树

---

练手板子题

代码如下：

#include 
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;
}
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

行列式

行列式，是一种对于矩阵的特殊形式——方阵的表示形式。所谓方阵，就是$n\times n$的矩阵。

一个 $n\times n$ 的方阵 $A$ 的行列式记为 $\det (A)$ 或者 $|A|$，一个 $2\times 2$ 矩阵的行列式可表示如下：
det ⁡ ( a b c d ) = a d − b c \det

=ad-bc det(ac​bd​)=ad−bc
把一个 $n$ 阶行列式中的元素 $a_{ij}$ 所在的第$i$行和第$j$列划去后，留下来的 $n-1$ 阶行列式叫做元素 $a_{ij}$ 的余子式，记作 $M_{ij}$。记 $A_{ij}=(-1{)}^{i+j}{M}_{ij}$，叫做元素 $a_{ij}$ 的代数余子式。

一个 $n\times n$ 矩阵的行列式等于其任意行（或列）的元素与对应的代数余子式乘积之和，即：
$$\det (A)=a_{i1}{A}_{i1}+\cdots +a_{in}+A_{in}=\sum _{j=1}^n{a}_{ij}(-1{)}^{i+j}\det (A_{ij})$$
代码实现：

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

高斯消元

前置芝士

三角矩阵

上三角矩阵的对角线左下方的系数全部为 $0$，下三角矩阵的对角线右上方的系数全部为 $0$。三角矩阵可以看作是一般方阵的一种简化情形。由于带三角矩阵的矩阵方程容易求解，在解多元线性方程组时，总是将其系数矩阵通过初等变换化为三角矩阵来求解。

举个栗子，下面的矩阵 $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=

U= ​u1,1​00⋮0​u1,2​u2,2​0⋮0​u1,3​u2,3​⋱0⋯​⋯⋯⋱⋱0​u1,n​u2,n​⋮un−1,n​un,n​​ ​

增广矩阵

又称扩增矩阵，就是在系数矩阵的右边添上一列，这一列是线性方程组的等号右边的值。

高斯消元

基本思想

通过一系列的加减消元运算，将方程组化为上三角矩阵。然后再逐一回代求出 $x$。

实现过程

解方程：
{ 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

⎩ ⎨ ⎧​3x1​+2x2​+x3​=62x1​+2x2​+2x3​=44x1​−2x2​−2x3​=2​
我们把这个方程组写成增广矩阵的形式：