- 2025-01-09切比雪夫距离(oiwiki学习)
oiwiki——距离切比雪夫距离(Chebyshevdistance):对于两个\(n\)维向量\(\vec{x}=(x_1,x_2,...,x_n)\)与\(\vec{y}=(y_1,y_2,...,y_n)\),定义它们之间的切比雪夫距离为\(\max{|x_i-y_i|}\)。切比雪夫距离与曼哈顿距离的联系以二维情况讨论:\((i)\)将每一个点\((x,y)\)
- 2025-01-08多项式全家桶
不知道什么时候写封装,有空就写。FWT:link。FWT同时带给我们一个深切的见解:一切多项式算法都是把多项式卷积转化成可以点积,再逆回去。FFTFFT处理实数意义下的多项式\((+,\times)\)卷积。也就是多项式乘法。点值表示法和系数表示法不必赘述了。对于两个以系数表示法表示的
- 2025-01-07线性代数10.矩阵的初等变换&矩阵的标准形
10.矩阵的初等变换10.1矩阵初等变换的规则对于任意存在第\(i,j\)两行、或第\(i,j\)两列的矩阵,满足以下初等变换规则:10.1.1对调对调\(i,j\)两行,记为:\(r_i\leftrightarrowr_j\)对调\(i,j\)两列,记为:\(c_i\leftrightarrowc_j\)以上运算均可逆10.1.2乘以\(k\)(\(k\in
- 2025-01-06线性代数9.矩阵的逆-分块矩阵
9.矩阵的逆-分块矩阵9.1分块矩阵的加法设矩阵\(A、B均为m\timesn\)的矩阵,且A、B均按相同的方式划分为\(s\timest\)块,其中:\[A=\begin{bmatrix}A_{11}&...&A_{1t}\\&...&\\A_{s1}&...&A_{st}\\\end{bmatrix}\]\[B=\begin{bmatrix}B_{11}&...&B_
- 2025-01-05线性代数8.矩阵的逆-相关性质&特殊矩阵&算法应用
8.矩阵的逆8.1相关性质性质1:若矩阵A可逆,则\(A^{-1}\)也可逆:\[(A^{-1})^{-1}=A\]性质1的证明:\(A\cdotA^{-1}=E\)性质2:若矩阵A可逆,则\(\lambda\cdotA\)也可逆:\[(\lambda\cdotA)^{-1}=\frac{1}{\lambda}\cdotA^{-1}\]性质2的证明:\(\lambda\cdotA\cdot\fra
- 2025-01-05线性代数7.矩阵的逆-定义&定理
7.矩阵的逆-定义和定理7.1逆矩阵的定义对于n阶矩阵A,存在一个n阶矩阵B,使:\[AB=BA=E\]则称矩阵A是可逆的。且B是A的逆矩阵,简称“逆阵”,记为:\[B=A^{-1}\]7.2对逆矩阵的理解若存在矩阵\(A_{n×n}\)、\(x_{n×1}\)、\(b_{n×1}\),使:\[b=Ax\]又存在矩阵\(B_{n×n}\),使:\[AB=E
- 2025-01-03线性代数入门
目录线性代数入门常识向量线性组合与张成空间线性相关基矩阵求逆高斯消元线性基随机化检验方法Schwartz–Zippel引理行列式积和式行列式的多种求法一、定义式二、高斯消元法三、余子式&Laplace展开四、Cauchy-Binet公式五、分块矩阵法组合意义应用伴随矩阵LGV引理矩阵\(M\)的
- 2024-12-31矩阵
基本概念矩阵基本概念\(\begin{bmatrix}a_{11}&a_{12}&...&a_{1n}\\a_{21}&a_{22}&...&a_{2n}\\\cdots&\cdots&\cdots&\cdots\\a_{m1}&a_{m2}&\cdots&a_{mn}\\\end{bmatrix}\)称
- 2024-12-27线性代数1.矩阵的基本概念&意义&特殊矩阵&基本运算
1.矩阵的基本概念&意义&特殊矩阵&基本运算1.1矩阵的定义:矩阵是由\(m\timesn\)个数排成的数表。如以下矩阵:\[X=\begin{bmatrix}x_{11}&x_{12}&x_{13}&...&x_{1n}\\x_{21}&x_{22}&x_{23}&...&x_{2n}\\x_{31}&x_{32}&x_{
- 2024-12-25P1306 斐波那契公约数
P1306斐波那契公约数对于Fibonacci数列:\[f_i=\begin{cases}[i=1]&i\leq1\\f_{i-1}+f_{i-2}&i\gt1\end{cases}\]请求出\(f_n\)与\(f_m\)的最大公约数,即\(\gcd(f_n,f_m)\)。数据规模与约定对于\(100\%\)的数据,保证\(1\l
- 2024-12-2513矩阵的逆
1.逆矩阵的定义对于n阶矩阵A,存在一个n阶矩阵B,使:$$AB=BA=E$$则称矩阵A是可逆的。且B是A的逆矩阵,简称“逆阵”,记为:$$B=A^{-1}$$2.对逆矩阵的理解若存在矩阵$A_{n×n}$、$x_{n×1}$、$b_{n×1}$,使:$$b=Ax$$又存在矩阵$B_{n×n}$,使:$$AB=E$$则:$$Bb=ABx\\Rightar
- 2024-12-25SVD分解的几何意义
本文翻译自https://www.ams.org/publicoutreach/feature-column/fcarc-svd仅用于研究及学习介绍本文主题singluarvaluedecomposition(奇异值分解,下文简称SVD)原本应当是本科课程的一部分,但却总是被忽视。除却相当的直观性,这些分解同样极其拥有应用价值。如,在线电影
- 2024-12-24省选集训 day 2 平衡树
A注意到每条运动轨迹是已知的,我们的目标就是找到可以选择的最大权值(定义为路径上的特殊点个数)的运动轨迹并支持删除这些点。找轨迹:利用斜率为\(\pm1\)的直线\(x+y,x-y\)至少有一个不变的性质寻找对于边界,可以使用常见手段:延拓一倍平面,也就是变成\(2n\)行,这样就只会走模
- 2024-12-242025省选集训
美妙集训。day1https://www.becoder.com.cn/contest/5894A用支持全局加1的Trie维护每个点的所有儿子的情况,父亲单独看。B观察、打表发现一棵满二叉树的sg等于层数的lowbit。CDE问题等价于平面上有若干\([a,b]\times[b,c](a\leb\lec)\)的带权矩形,求覆盖某个点
- 2024-12-21[NOI Online #3 提高组] 魔法值
思路讲真现在脑子胡的依托转化题意,给定一个无自环无重边的\(n\)点\(m\)边的图,每天每个城市的魔法值都会变成其连边城市的魔法值的\(\oplus\),求\(a_i\)天后,\(H\)点的魔法值看到题目给的柿子和\(a_i\leq2^{32}\)感觉就要用矩快这是一种异或矩快,也就是在
- 2024-12-17X.3 一维梁
X.3一维梁一维连续系统本图中,w表示梁在z方向的挠度(deflection,或位移),f表示每单元长度受到的横向力(transverseforce),T表示弦(string)受到的张力。对于一维张紧弦,其控制方程为:\[\begin{equation}T\frac{d^2w}{dx^2}+f\begin{pmatrix}x\end{pmatrix}=0\end{equation}\]
- 2024-12-14转载:【AI系统】Winograd 算法
在上一篇文章的介绍中,介绍了Im2Col技术,它通过将三维张量重新排列成矩阵形式,然后利用基于内存访问局部性的优化库如GEMM(通用矩阵乘法库)加速计算。随后,还探讨了空间组合优化,这一种利用局部性原理来提升效率的技术。在本文将重点介绍Winograd优化算法,它是矩阵乘优化方法中Copp
- 2024-12-13转载:【AI系统】Winograd 算法
在上一篇文章的介绍中,介绍了Im2Col技术,它通过将三维张量重新排列成矩阵形式,然后利用基于内存访问局部性的优化库如GEMM(通用矩阵乘法库)加速计算。随后,还探讨了空间组合优化,这一种利用局部性原理来提升效率的技术。在本文将重点介绍Winograd优化算法,它是矩阵乘优化方法中Copp
- 2024-12-12转载:【AI系统】Winograd 算法
在上一篇文章的介绍中,介绍了Im2Col技术,它通过将三维张量重新排列成矩阵形式,然后利用基于内存访问局部性的优化库如GEMM(通用矩阵乘法库)加速计算。随后,还探讨了空间组合优化,这一种利用局部性原理来提升效率的技术。在本文将重点介绍Winograd优化算法,它是矩阵乘优化方法中Copp
- 2024-12-12转载:【AI系统】Winograd 算法
在上一篇文章的介绍中,介绍了Im2Col技术,它通过将三维张量重新排列成矩阵形式,然后利用基于内存访问局部性的优化库如GEMM(通用矩阵乘法库)加速计算。随后,还探讨了空间组合优化,这一种利用局部性原理来提升效率的技术。在本文将重点介绍Winograd优化算法,它是矩阵乘优化方法中Copp
- 2024-12-09【机器学习】在向量的流光中,揽数理星河为衣,以线性代数为钥,轻启机器学习黎明的瑰丽诗章
文章目录线性代数入门:机器学习零基础小白指南前言一、向量:数据的基本单元1.1什么是向量?1.1.1举个例子:1.2向量的表示与维度1.2.1向量的维度1.2.2向量的表示方法1.3向量的基本运算1.3.1向量加法1.3.2向量的数乘1.3.3向量的长度(范数)1.4向量的几何意义二、矩阵
- 2024-12-09第二类斯特林数小记
随便记点。定义第二类StirlingNumber。latex:$\begin{Bmatrix}n\\m\end{Bmatrix}$或n\bracem,大小渲染可能有差别。我们定义\(\begin{Bmatrix}n\\m\end{Bmatrix}\)表示将\(n\)个不同的球放进\(m\)个相同非空盒子的方案数。求法考虑类似DP地求出\(\begin{Bmatrix
- 2024-12-08置换与转置 permutations & transposes
置换与转置permutations&transposes 首先说一下置换矩阵(permutationmatrix),通常记为\(\symbfit{P}\),是用来完成行互换操作的矩阵。\(\symbfit{P}_{i,j}\)记为第\(i\)行和第\(j\)行互换的置换矩阵。 例如三行三列方阵有\(3!=6\)个置换矩阵,如\(\symbfit{P}_{2,1}=\begin{bm
- 2024-12-06矩阵快速幂优化
矩阵快速幂是一种常用于DP的算法。通过矩阵乘法去快速转移状态求解。但是由于矩阵运算的复杂度极高,因此一般而言矩阵快速幂优化DP的决策点不能太多。矩阵快速幂的另一种应用是图论中的路径经过方案数的问题具体来讲有一个结论:邻接矩阵的k次方表示某两个点之间路径距离为k的
- 2024-12-03设计位置编码
Gall定律一个有效的复杂系统通常是从一个有效的简单系统演化而来的——JohnGall本文将带你一步步探究Transformer模型中先进的位置编码技术。我们将通过迭代改进编码位置的方法,最终得出旋转位置编码(RotaryPostionalEncoding,RoPE),这也是最新发布的LLama3.2和