建议先把具体数学笔记
看一遍
线性代数
线性空间: 在一个数域上，关于加法和数乘的封闭空间
秩: 线性独立的纵列的极大数，通常表示为
r
k
(
A
)
rk(A)
rk(A)或
r
a
n
k
(
A
)
rank (A)
rank(A)
基(基底): 基元素成为称为基向量，向量空间里的任意一个元素，都可以唯一的表示成基向量的线性组合
余子式: A A A关于 ( i , j ) (i,j) (i,j)的余子式 M i , j M_{i,j} Mi,j?是去掉第 i i i行第 j j j列的矩阵行列式
代数余子式:
C i , j = ( ? 1 ) i + j M i , j C_{i,j}=(-1)^{i+j}M_{i,j} Ci,j?=(?1)i+jMi,j?
伴随矩阵:
C
C
C的转置
A
?
A^*
A?称为
A
A
A的伴随矩阵
一些性质
- A A A可逆当且仅当 A ? A^* A?可逆
-
A
?
=
∣
A
∣
A
?
1
A^*=|A|A^{-1}
A?=∣A∣A?1
-
逆矩阵
在原矩阵右边放一个单位矩阵然后跑高斯消元
可以快速求解
A
x
=
B
Ax=B
Ax=B
行列式
∣
A
∣
=
∑
p
∈
σ
n
(
?
1
)
s
g
n
(
p
)
∏
A
i
,
p
[
i
]
|A|=\sum_{p \in \sigma_n}(-1)^{sgn(p)}\prod A_{i,p[i]}
∣A∣=p∈σn?∑?(?1)sgn(p)∏Ai,p[i]?
行列式七大性质：
- 1.行列式和它的转置行列式相等。
- 2.行列式中某一行元素的公因子可以提到行列式符号的外边来。或者说，用一个数来乘行列式，可以把这个数乘到行列式的某一行上。
- 3.若果行列式中有一行元素全为零，则行列式的值为零。
- 4.交换行列式两行，行列式仅改变符号。
- 5.若行列式中有两行完全相同，则这个行列式的值为零。
- 6.若行列式有两行的对应元素成比例，则这个行列式等于零。
- 7.把行列式某一行的元素乘以同于个数后加到另一行的对应元素上，行列式不变。
LGV 引理
矩阵树定理
就是度数矩阵-邻接矩阵后，去掉一个点的行列式
令 g [ i ] [ j ] g[i][j] g[i][j]为从 i 到 j i到j i到j的边数的相反数， g [ i ] [ i ] g[i][i] g[i][i]为 i i i的入度，那么以 i i i号节点为根的生成树个数就是去掉第 i i i行第 i i i列的行列式
BEST定理
n
个
点
有
向
图
欧
拉
回
路
的
条
数
为
任
意
一
个
点
的
树
形
图
乘
上
(
点
度
数
?
1
)
！
的
乘
积
n 个点有向图欧拉回路的条数为任意一个点的树形图乘上(点度数-1)！的乘积
n个点有向图欧拉回路的条数为任意一个点的树形图乘上(点度数?1)！的乘积
e
c
(
G
)
=
t
w
(
G
)
∏
(
d
e
g
(
v
)
?
1
)
!
ec(G)=t_w(G)\prod(deg(v)-1)!
ec(G)=tw?(G)∏(deg(v)?1)!
band-matrix(带状矩阵消元)
Froggy写的好好呀
浅谈高斯消元拓展之 band-matrix
其实就是限制一个band区间，然后每次交换，消元都在这个区间里就行了
向右消元要band*2
特征值与特征多项式
线性变换的特征向量在变换后方向不变，缩放比例即为特征值
A
v
?
=
λ
v
?
A\vec{v}=λ\vec{v}
Av=λv
那么称
λ
λ
λ是
A
A
A的特征值，
v
?
\vec{v}
v是
A
A
A的特征向量
显然可以得到
A
v
?
=
(
λ
I
)
v
?
A\vec{v}=(λI)\vec{v}
Av=(λI)v
(
A
?
λ
I
)
v
?
=
0
?
(A-λI)\vec{v}=\vec{0}
(A?λI)v=0
即 ∣ ( A ? λ I ) ∣ = 0 |(A-λI)|=0 ∣(A?λI)∣=0
相似与对角化
假设存在若干线性无关的特征向量
x
1
,
x
2
,
.
.
,
x
n
x_1,x_2,..,x_n
x1?,x2?,..,xn?
令
Q
=
[
x
1
,
x
2
,
.
.
.
,
x
n
]
Q=[x_1,x_2,...,x_n]
Q=[x1?,x2?,...,xn?]
那么必定存在
Q
?
1
A
Q
=
D
Q^{-1}AQ=D
Q?1AQ=D
D为对角矩阵(对角线上的为特征值)
然后就可以加速矩阵快速幂了
O
(
n
3
+
n
l
o
g
k
)
O(n^3+nlogk)
O(n3+nlogk)
什么意思呢？
考虑乘
Q
Q
Q代表什么，代表在原坐标系上将基向量变为特征基的一组线性变换
所以乘
Q
?
1
Q^{-1}
Q?1表示的是将原坐标系转为以特征基作为向量基的新坐标
然后在新坐标上进行
A
A
A变换，再把它转回原坐标
意思就是以特征基作为单位基做 A A A的变换，因为前面说了向量只是缩放，所以一定是对角矩阵
然后再用特征基乘上这个对角矩阵，然后在转回原单位基即可
A k = Q D k Q ? 1 A^k=Q D^k Q^{-1} Ak=QDkQ?1
特征多项式
概率和期望
期望的线性性
对于两个随机变量
X
,
Y
X,Y
X,Y,有
E
[
X
+
Y
]
=
E
[
X
]
+
E
[
Y
]
E[X+Y]=E[X]+E[Y]
E[X+Y]=E[X]+E[Y]
多做题吧
min-max容斥
E [ m a x ( S ) ] = ∑ T ? S ( ? 1 ) ∣ T ∣ ? 1 E [ m i n ( T ) ] E[max(S)]=\sum_{T?S}(-1)^{|T|-1}E[min(T)] E[max(S)]=T?S∑?(?1)∣T∣?1E[min(T)]
一般定义 E [ m a x ( S ) ] E[max(S)] E[max(S)]为把这个集合全部都经过的期望, E [ m i n ( S ) ] E[min(S)] E[min(S)]为第一次到这个集合到期望
然后套 min ? ? max ? \min-\max min?max容斥
容易发现容斥的式子是一个高维前缀和，所以可以用 F M T FMT FMT优化成 O ( n 2 n ) O(n2^n) O(n2n)
min,max反过来同样成立
组合计数
十二重计数法（十二试炼）
LLA
m n m^n mn
ULA
方程非负整数解个数
(
n
+
m
?
1
m
?
1
)
\binom{n+m-1}{m-1}
(m?1n+m?1?)
ULB
方程正整数解个数
(
n
?
1
m
?
1
)
\binom{n-1}{m-1}
(m?1n?1?)
LLC
m n m^{n\over{}} mn?
ULC
( n m ) \binom{n}{m} (mn?)
LUC
[ n ≤ m ] [n \le m] [n≤m]
UUC
[ n ≤ m ] [n \le m] [n≤m]
LLB
S ( n , m ) m ! S(n, m)m! S(n,m)m!
LUB
S ( n , m ) S(n,m) S(n,m)
LUA
∑ i = 0 m S ( n , i ) \sum_{i=0}^m S(n,i) i=0∑m?S(n,i)
UUB
UUB
二分图带权匹配计数
先咕咕咕着
斯特林数
看之前写的吧