CSP-S初赛基础知识整理
RT
持续更新中
关于部分
l
a
t
e
x
latex
latex 在 csdn 不能很好的显示,更好的阅读体验。
[1]计算机基础知识
计算机系统的组成
硬件系统和软件系统。
计算机硬件的五大组成
控制器、运算器、存储器、输入设备和输出设备。
[1-2]进制及其转化和运算
[1-2]二进制
[1]基本定义及应用
逢二进一。后缀为
B
\texttt{B}
B。
是计算机主要存储方式。
[1]基本运算
- 加法 0+0=0,0+1=1,1+1=10。
- 减法 0-0=0,1-0=1,1-1=0。
- 乘法 0×0=0,0×1=0,1×0=0,1×1=1。
[2]位运算
- and(&)
0 | 1 | |
---|---|---|
0 | 0 | 0 |
1 | 0 | 1 |
- or(|)
0 | 1 | |
---|---|---|
0 | 0 | 1 |
1 | 1 | 1 |
- xor(^)
0 | 1 | |
---|---|---|
0 | 0 | 1 |
1 | 1 | 0 |
- not(~)
0 | 1 |
---|---|
1 | 0 |
[1]其他进制及转换
八进制
有
0
→
7
0\to7
0→7 8个字符组成,与二进制1换3。
后缀为
O
\texttt{O}
O。
2进制 | 8进制 |
---|---|
000 | 0 |
001 | 1 |
010 | 2 |
011 | 3 |
100 | 4 |
101 | 5 |
110 | 6 |
111 | 7 |
十六进制
有
0
→
9
,
A
→
F
0\to9,A\to F
0→9,A→F 16个字符组成,与二进制1换4。
后缀为
O
\texttt{O}
O。
2进制 | 8进制 |
---|---|
0000 | 0 |
0001 | 1 |
0010 | 2 |
0011 | 3 |
0100 | 4 |
0101 | 5 |
0110 | 6 |
0111 | 7 |
1000 | 8 |
1001 | 9 |
1010 | A |
1011 | B |
1100 | C |
1101 | D |
1110 | E |
1111 | F |
十进制
有
0
→
9
0\to9
0→9 10个字符组成。
后缀为
D
\texttt{D}
D。
2进制 | 10进制 |
---|---|
0000 | 0 |
0001 | 1 |
0010 | 2 |
0011 | 3 |
0100 | 4 |
0101 | 5 |
0110 | 6 |
0111 | 7 |
1000 | 8 |
1001 | 9 |
1010 | 10 |
1011 | 11 |
1100 | 12 |
1101 | 13 |
1110 | 14 |
1111 | 15 |
[1]主要人物及贡献
名字 | 国籍 | 信息学主要贡献 | 称号身份 |
---|---|---|---|
艾伦·麦席森·图灵 | 英 | 图灵机,图灵奖,图灵实验 | 计算机科学之父,人工智能之父 |
约翰·冯·诺依曼 | 美籍匈牙利 | 体系构想,程序存放于内存 | 计算机之父、博弈论之父 |
克劳德·艾尔伍德·香农 | 美 | 提出了信息熵的概念 | 信息论的创始人 |
姚期智 | 中 | 通讯复杂度,伪随机数生成 | 奠定现代密码学 |
艾达·拉芙蕾丝 | 英 | Ada语言 | 第一个程序员,计算机程序创始人 |
[5]Linux
命令 | 作用 |
---|---|
mkdir | 创建目录 |
cp | 复制文件(夹) |
rm | 删除文件(夹) |
mv | 重命名/移动 |
cd | 切换工作目录 |
pwd | 打印目录路径 |
ls | 显示目录文件 |
time | 测量运行时间 |
g++ | 编译命令 |
gdb | 调试命令 |
./a | 运行 a |
time
real time > cpu time = user time + sys time
real time
表示从程序开始到程序执行结束时所消耗的时间,包括CPU的用时。
user time
值表示程序本身,以及它所调用的库中的子例程使用的时间。
sys time
是由程序直接或间接调用的系统调用执行的时间。
gdb
默认
gdb ./a
对 a \texttt{a} a 进行调试。
gdn --args ./a 1.txt
对 a \texttt{a} a 进行调试并标记输入文件为 1.txt \texttt{1.txt} 1.txt。
其他操作
b(reak)
设置断点。
display
查看变量或式的值。
c(ontinue)
开始连续(而非单步)执行。
s(ept)
进入函数调试。
[5]编译选项
默认
g++ 1.cpp -o 1.exe
其中 1.cpp \texttt{1.cpp} 1.cpp 为源文件, 1.exe \texttt{1.exe} 1.exe 为输出文件。
额外编译指令
-x language filename
将 filename \texttt{filename} filename 这个文件以 language \texttt{language} language 的语言编译。
注意:-x
指令对其之后的所有文件都生效。
-x none filename
取消上一个指令的效果。
-c
只将文件生成为 obj \texttt{obj} obj (二进制)文件。
-S
只将文件生成为汇编代码。
-o
标记输出文件。
-
-O0
,-O1
,-O2
,-O3
开启 O0(1,2,3) \texttt{O0(1,2,3)} O0(1,2,3)优化。
-g
产生调试信息。
[5]STL
STL
[5-8]算法
[6]复杂度分析
空间复杂度分析
时间复杂度分析
主定理
令 T ( n ) = a × T ( n b ) + f ( n ) T(n)=a\times T(\frac{n}{b})+f(n) T(n)=a×T(bn)+f(n)
当 a ≥ 1 a n d b > 1 a\geq 1\ and\ b > 1 a≥1 and b>1 时
-
若 ∃ ϵ > 0 \exists\epsilon > 0 ∃ϵ>0,有 f ( n ) = O ( n log b a − ϵ ) f(n)=O\left(n^{\log_{\ b}{\ a-\epsilon}}\right) f(n)=O(nlog b a−ϵ),则 T ( n ) = Θ ( n log b a ) T(n)=\Theta\left(n^{\log_{\ b}{\ a}}\right) T(n)=Θ(nlog b a)。
-
若有 f ( n ) = O ( n log b a ) f(n)=O\left(n^{\log_{\ b}{\ a}}\right) f(n)=O(nlog b a),则 T ( n ) = Θ ( n log b a log n ) T(n)=\Theta\left(n^{\log_{\ b}{\ a}}\log{n}\right) T(n)=Θ(nlog b alogn)。
-
若 ∃ ϵ > 0 \exists\epsilon > 0 ∃ϵ>0,有 f ( n ) = O ( n log b a + ϵ ) f(n)=O\left(n^{\log_{\ b}{\ a+\epsilon}}\right) f(n)=O(nlog b a+ϵ) 且对于常数 c < 1 c<1 c<1 和所有足够大的 n n n,有 a × f ( n b ) ≤ c × f ( n ) a\times f(\frac{n}{b})\leq c\times f(n) a×f(bn)≤c×f(n),则 T ( n ) = Θ ( f ( n ) ) T(n)=\Theta\left(f(n)\right) T(n)=Θ(f(n))。
[6]基础算法
分治算法
[5-6]排序算法
排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 | 稳定性 | 评级 |
---|---|---|---|---|---|---|---|
归并排序 | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n ) \Theta\left({n}\right) Θ(n) | 非原地排序 | 稳定 | 5 |
快速排序 | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n 2 ) \Theta\left({n^2}\right) Θ(n2) | Θ ( log n ) \Theta\left({\log{n}}\right) Θ(logn) | 原地排序 | 不稳定 | 5 |
基数排序 | Θ ( n × k ) \Theta\left({n\times k}\right) Θ(n×k) | Θ ( n × k ) \Theta\left({n\times k}\right) Θ(n×k) | Θ ( n × k ) \Theta\left({n\times k}\right) Θ(n×k) | Θ ( n + k ) \Theta\left({n + k}\right) Θ(n+k) | 非原地排序 | 稳定 | 6 |
堆排序 | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( 1 ) \Theta\left({1}\right) Θ(1) | 原地排序 | 不稳定 | 6 |
桶排序 | Θ ( n + k ) \Theta\left({n + k}\right) Θ(n+k) | Θ ( n + k ) \Theta\left({n + k}\right) Θ(n+k) | Θ ( n 2 ) \Theta\left({n^2}\right) Θ(n2) | Θ ( n + k ) \Theta\left({n + k}\right) Θ(n+k) | 非原地排序 | 稳定 | 5 |
树形选择排序(竞标赛排序) | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n log n ) \Theta\left({n\log{n}}\right) Θ(nlogn) | Θ ( n ) \Theta\left({n}\right) Θ(n) | 非原地排序 | 不稳定 | 6 |
[5]字符串
KMP
时空复杂度
时间复杂度为 Θ ( n + m ) \Theta\left({n+m}\right) Θ(n+m),空间复杂度为 Θ ( m ) \Theta\left({m}\right) Θ(m)。
基本代码
#include<bits/stdc++.h>
using namespace std;
int ans[1000039],lena,lenb;
char a[1000039],b[1000039];
int main(){
register int i,j;
cin>>a>>b;lena=strlen(a);lenb=strlen(b);
for(i=1;i<lenb;i++){
while(j&&b[i]!=b[j+1])j=ans[j];
if(b[j+1]==b[i])j++;
ans[i]=j;
}
j=0;
for(i=0;i<lena;i++){
while(j>0&&b[j+1]!=a[i])j=ans[j];
if(b[j+1]==a[i])j++;
if(j==lenb){
printf("%d\n",i-lenb+1);
j=ans[j];
}
}
for(i=1;i<=lenb;i++)printf("%d ",ans[i]);
return 0;
}
[6-8]搜索
时间复杂度基本为常数优化。
[6]减枝搜索
[6]记忆化搜索
[7]启发式搜索
[7]双向BFS搜索
[7]迭代加深搜索
[8]搜索对象压缩搜索
[6-7]图论
[6]Prim 和 kruskal 最小生成树
kruskal 时空复杂度
时间复杂度为 Θ ( m log m ) \Theta\left({m\log{m}}\right) Θ(mlogm),空间复杂度为 Θ ( n + m ) \Theta\left({n+m}\right) Θ(n+m)。
kruskal 基本代码
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,f[200039],tot;
struct node{int u,v,w;bool operator<(node x)const{return w<x.w;}}a[200039];
int find(int x){return f[x]=f[x]^x?find(f[x]):x;}
void kruskal(){
int x,y;
for(int i=1;i<=m;i++){
x=find(a[i].u);
y=find(a[i].v);
if(x==y) continue;
else{
ans+=a[i].w;
f[x]=y;
tot++;
if(tot==n-1) break;
}
}
}
int main(){
scanf("%d%d",&n,&m);
register int i,j;
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=m;i++)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
sort(a+1,a+m+1);kruskal();
if(tot==n-1)printf("%d",ans);
else printf("orz");
return 0;
}
[7]次小生成树
[6]Dojkstra、bellman_ford 和 SPFA 单源最短路
[7]单源次短路
[6]Floyd-Warshall 求最短路和传递闭包
[6]DAG拓扑排序
[6]欧拉道路和欧拉回路
[6]二分图构造和判定
[6]最近公共祖先
倍增LCA 时空复杂度
时间复杂度为预处理 Θ ( n log 树高 ) \Theta\left({n\log{树高}}\right) Θ(nlog树高),查询 Θ ( log 树高 ) \Theta\left({\log{树高}}\right) Θ(log树高)。
空间复杂度为 Θ ( n log 树高 ) \Theta\left({n\log{树高}}\right) Θ(nlog树高)。
倍增LCA 基本代码
#include<bits/stdc++.h>
using namespace std;
int n,m,root,x,y,d[500039];
int Fa[500039][39];
vector<int>v[500039];
void dfs(int u,int deep,int fa){
d[u]=deep;int k=1;Fa[u][0]=fa;
do{Fa[u][k]=Fa[Fa[u][k-1]][k-1];}while(Fa[u][k++]);
for(int i=0;i<v[u].size();i++)if(v[u][i]^fa)dfs(v[u][i],deep+1,u);
}
int LCA(int u,int v){
int k=19;
while(d[u]<d[v]){while(d[u]>d[Fa[v][k]]&&k)k--;v=Fa[v][k];}
if(u==v)return x;k=20;
while(k--){if(Fa[u][k]!=Fa[v][k])u=Fa[u][k],v=Fa[v][k];}
return Fa[u][0];
}
int main(){
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(root,0,0);d[0]=-1;
while(m--){
scanf("%d%d",&x,&y);
if(d[x]>d[y])x^=y^=x^=y;
printf("%d\n",LCA(x,y));
}
}
[7]求强连通分量
[7]强连通分量缩点
[7]求割点割边
[6-8]动态规划
[6]树形动态规划
[7]状态压缩动态规划
[8]动态规划优化
斜率优化DP
四边形不等式优化DP
二维四边形不等式优化区间DP
CDQ分治优化DP
[5-7]数学知识
[5-6]高中数学
[5]代数
[6]解析几何
[6]立体几何
[5-7]初等数论
[5]同余式
[7]欧拉定理和欧拉函数
欧拉函数
φ ( n ) \varphi(n) φ(n) 表示小于n的正整数与n互质的数的个数。
当n为质数时 φ ( n ) = n − 1 \varphi(n)=n-1 φ(n)=n−1
当n为奇数时 φ ( 2 n ) = φ ( n ) \varphi(2n)=\varphi(n) φ(2n)=φ(n)
当 gcd ( a , b ) = 1 \gcd(a,b)=1 gcd(a,b)=1时 φ ( a b ) = φ ( a ) φ ( b ) \varphi(ab)=\varphi(a)\varphi(b) φ(ab)=φ(a)φ(b)
欧拉定理
当 gcd ( a , p ) = 1 \gcd(a,p)=1 gcd(a,p)=1时 a φ ( p ) ≡ 1 ( m o d p ) a^{\varphi(p)}\equiv1(mod\ p) aφ(p)≡1(mod p)
[7]费马小定理
a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv1(mod\ p) ap−1≡1(mod p)
[7]威尔逊定理
当且仅当 p p p 为素数时 ( p − 1 ) ≡ − 1 ( m o d p ) (p-1)\equiv-1(mod\ p) (p−1)≡−1(mod p)。
[7]斐蜀定理
当 a , b ≠ 0 a,b\not=0 a,b=0 时, ∃ x , y ∈ Z \exists x,y\in \mathbb{Z} ∃x,y∈Z 满足 a x + b y = gcd ( a , b ) ax+by=\gcd(a,b) ax+by=gcd(a,b)。
[7]逆元
当 gcd ( a , b ) ≠ 0 \gcd(a,b)\not=0 gcd(a,b)=0 时, ( a / b ) m o d p (a/b)mod\ p (a/b)mod p 可转换为 a ∗ b p − 2 m o d p a*b^{p-2}mod\ p a∗bp−2mod p
[7]扩展欧几里得
[7]中国剩余定理
[6-7]组合数学
[6]可重集排列
对于一个有 n n n 个元素共 k k k 种的集合,其中每种元素分别有 p 1 , p 2 ⋯ p k p_1,p_2\cdots p_k p1,p2⋯pk 个,那么可重集排列数量为
n ! ∏ i − 1 k p i ! \frac{n!}{\prod_{i-1}^{k}p_i!} ∏i−1kpi!n!
[6]可重集组合
对于一个有 n n n 个元素的集合,每次选 k k k 个,允许元素重复,且不计顺序的可重集组合数量为
( n + r − 1 r ) \left(\begin{array}{}n+r-1\\r\\\end{array}{}\right) (n+r−1r)
[6]错排、圆排
错排
一个长度为 n n n 的排列且满足 ∀ i ∈ [ 1 , n ] \forall i\in[1,n] ∀i∈[1,n] 第 i i i 个数不为 i i i 的数量为
递推式
D n = n D n − 1 + − 1 n , D 1 = 0 D_n=nD_{n-1}+{-1}^n,D_1=0 Dn=nDn−1+−1n,D1=0
通项式
D n = ∑ k = 0 n ( n k ) ( n − k ) ! ( − 1 ) k D_n=\sum_{k=0}^{n}\left(\begin{array}{}n\\k\\\end{array}{}\right)(n-k)!(-1)^k Dn=k=0∑n(nk)(n−k)!(−1)k
圆排
从 n n n 个元素中选 r r r 个进行圆排列的数量为
n ! r × ( n − r ) ! \frac{n!}{r\times(n-r)!} r×(n−r)!n!
[6]鸽巢原理
[6]二项式定理
( x + y ) n = ( n 0 ) x n y 0 + ( n 1 ) x n − 1 y 1 + ( n 2 ) x n − 2 y 2 + ⋯ ⋯ + ( n n − 1 ) x 1 y n − 1 + ( n n ) x 0 y n n ∈ Z + (x+y)^n=\left(\begin{array}{}n\\0\\\end{array}{}\right)x^ny^0+\left(\begin{array}{}n\\1\\\end{array}{}\right)x^{n-1}y^1+\left(\begin{array}{}n\\2\\\end{array}{}\right)x^{n-2}y^2+\cdots\cdots+\left(\begin{array}{}n\\n-1\\\end{array}{}\right)x^1y^{n-1}+\left(\begin{array}{}n\\n\\\end{array}{}\right)x^0y^n\ \ \ {n\in\mathbb{Z^+}} (x+y)n=(n0)xny0+(n1)xn−1y1+(n2)xn−2y2+⋯⋯+(nn−1)x1yn−1+(nn)x0yn n∈Z+
( x + y ) n = [ x 0 ⋯ x n ] [ ( n 0 ) ⋱ ( n n ) ] [ 1 ⋮ 1 ] [ y 0 ⋮ y n ] n ∈ Z + (x+y)^n=\left[\begin{matrix}{}x^0\cdots x^n\\\end{matrix}{}\right]\left[\begin{matrix}{}\left(\begin{matrix}{}n\\0\\\end{matrix}{}\right)&&\\&\ddots&\\&&\left(\begin{matrix}{}n\\n\\\end{matrix}{}\right)\\\end{matrix}{}\right]\left[\begin{matrix}{}&&1\\&\vdots&\\1&&\\\end{matrix}{}\right]\left[\begin{matrix}{}y_0\\\vdots\\y_n\\\end{matrix}{}\right]\ \ \ {n\in\mathbb{Z^+}} (x+y)n=[x0⋯xn]⎣ ⎡(n0)⋱(nn)⎦ ⎤⎣ ⎡1⋮1⎦ ⎤⎣ ⎡y0⋮yn⎦ ⎤ n∈Z+
[7]容斥原理
[7]卡特兰数
C n + 1 = C 0 C n + C 1 C n − 1 + ⋯ + C n C 0 C_{n+1}=C_0C_n+C_1C_{n-1}+\cdots+C_nC_0 Cn+1=C0Cn+C1Cn−1+⋯+CnC0
[5-7]线性代数
[5]矩阵概念
[6]特殊矩阵
稀疏矩阵
三角矩阵
[6]矩阵的初等变换
[6]矩阵的加减乘和置换
矩阵加减法
[ a 1 , 1 a 1 , 2 ⋯ a 1 , m a 2 , 1 a 2 , 2 ⋮ ⋱ a n , 1 a n , m ] ± [ b 1 , 1 b 1 , 2 ⋯ b 1 , m b 2 , 1 b 2 , 2 ⋮ ⋱ b n , 1 b n , m ] = [ a 1 , 1 ± b 1 , 1 a 1 , 2 ± b 1 , 2 ⋯ a 1 , m ± b 1 , m a 2 , 1 ± b 2 , 1 a 2 , 2 ± b 2 , 2 ⋮ ⋱ a n , 1 ± b n , 1 a n , m ± b n , m ] \left[\begin{matrix}{}a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\a_{2,1}&a_{2,2}\\\vdots&&\ddots&\\a_{n,1}&&&a_{n,m}\\\end{matrix}{}\right]\pm\left[\begin{matrix}{}b_{1,1}&b_{1,2}&\cdots&b_{1,m}\\b_{2,1}&b_{2,2}\\\vdots&&\ddots&\\b_{n,1}&&&b_{n,m}\\\end{matrix}{}\right]=\left[\begin{matrix}{}a_{1,1}\pm b_{1,1}&a_{1,2}\pm b_{1,2}&\cdots&a_{1,m}\pm b_{1,m}\\a_{2,1}\pm b_{2,1}&a_{2,2}\pm b_{2,2}\\\vdots&&\ddots&\\a_{n,1}\pm b_{n,1}&&&a_{n,m}\pm b_{n,m}\\\end{matrix}{}\right] ⎣ ⎡a1,1a2,1⋮an,1a1,2a2,2⋯⋱a1,man,m⎦ ⎤±⎣ ⎡b1,1b2,1⋮bn,1b1,2b2,2⋯⋱b1,mbn,m⎦ ⎤=⎣ ⎡a1,1±b1,1a2,1±b2,1⋮an,1±bn,1a1,2±b1,2a2,2±b2,2⋯⋱a1,m±b1,man,m±bn,m⎦ ⎤
矩阵加减法满足交换律和结合律。
矩阵乘法
C n + 1 = C 0 C n + C 1 C n − 1 + ⋯ + C n C 0 C_{n+1}=C_0C_n+C_1C_{n-1}+\cdots+C_nC_0 Cn+1=C0Cn+C1Cn−1+⋯+CnC0
C
=
A
⋅
B
C
i
,
j
=
∑
k
=
1
p
A
i
,
k
B
k
,
j
C=A\cdot B\ \ \ \ C_{i,j}=\sum_{k=1}^{p}A_{i,k}B_{k,j}
C=A⋅B Ci,j=k=1∑pAi,kBk,j
[
a
1
,
1
a
1
,
2
⋯
a
1
,
p
a
2
,
1
a
2
,
2
⋮
⋱
a
m
,
1
a
m
,
p
]
⋅
[
b
1
,
1
b
1
,
2
⋯
b
1
,
n
b
2
,
1
b
2
,
2
⋮
⋱
b
p
,
1
b
p
,
n
]
=
[
∑
k
=
1
p
a
1
k
b
k
,
1
∑
k
=
1
p
a
1
,
k
b
k
,
2
⋯
∑
k
=
1
p
a
1
,
k
b
k
,
n
∑
k
=
1
p
a
2
,
k
b
k
,
1
∑
k
=
1
p
a
2
,
k
b
k
,
2
⋮
⋱
∑
k
=
1
p
a
m
,
k
b
k
,
1
∑
k
=
1
p
a
m
,
k
b
k
,
n
]
\left[\begin{matrix}{}a_{1,1}&a_{1,2}&\cdots&a_{1,p}\\a_{2,1}&a_{2,2}\\\vdots&&\ddots&\\a_{m,1}&&&a_{m,p}\\\end{matrix}{}\right]\cdot\left[\begin{matrix}{}b_{1,1}&b_{1,2}&\cdots&b_{1,n}\\b_{2,1}&b_{2,2}\\\vdots&&\ddots&\\b_{p,1}&&&b_{p,n}\\\end{matrix}{}\right]=\left[\begin{matrix}{}\sum_{k=1}^{p}a_{1k}b_{k,1}&\sum_{k=1}^{p}a_{1,k}b_{k,2}&\cdots&\sum_{k=1}^{p}a_{1,k}b_{k,n}\\\sum_{k=1}^{p}a_{2,k}b_{k,1}&\sum_{k=1}^{p}a_{2,k}b_{k,2}\\\vdots&&\ddots&\\\sum_{k=1}^{p}a_{m,k}b_{k,1}&&&\sum_{k=1}^{p}a_{m,k}b_{k,n}\\\end{matrix}{}\right]
⎣
⎡a1,1a2,1⋮am,1a1,2a2,2⋯⋱a1,pam,p⎦
⎤⋅⎣
⎡b1,1b2,1⋮bp,1b1,2b2,2⋯⋱b1,nbp,n⎦
⎤=⎣
⎡∑k=1pa1kbk,1∑k=1pa2,kbk,1⋮∑k=1pam,kbk,1∑k=1pa1,kbk,2∑k=1pa2,kbk,2⋯⋱∑k=1pa1,kbk,n∑k=1pam,kbk,n⎦
⎤文章来源:https://www.toymoban.com/news/detail-705504.html
矩阵乘法满足结合律,不满足交换律。文章来源地址https://www.toymoban.com/news/detail-705504.html
[6]线性方程组和高斯消元法
到了这里,关于CSP-S初赛基础知识整理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!