点值表示法 对于一个 $n-1$ 阶多项式 $P(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}$，如果我们已知一个点集 $S:\{(x_0,y_0),(x_1,y_1),\cdots,(x_{n-1},y_{n-1})\}$，点集 $S$ 中的所有点都满足 $y_i=P(x_i)$，且 $x_i(i=0,1,\c…

傅里叶级数的复数形式 推导 在傅里叶级数章节中，我们已知一个周期为 $2l$ 的周期函数可以展开为 $$f(x) = a_0 + \sum_{i=1}^{\infty}a_i \cos \frac{i\pi x}{l} + \sum_{i=1}^{\infty} b_i\sin \frac{i\pi x}{l}$$ 为了方便起见，我们作如下定义：常…

直线 定义 一般式 不像二维几何中，直线 $l$ 可以直接用一个方程 $ax+by=c$ 简单地表示，三维几何中 $ax+by+cz=d$ 表示一个平面。而直线可以表示为两个平面的交，即方程组 $$l:\begin{cases}\Pi_1: a_1x+b_1y+c_1z=d_1\\\Pi_2: a_2x+b_2y+c_2z=d_2\\\end{ca…

平面 定义 平面是满足方程 $ax+by+cz=d$ 的点 $(x,y,z)$ 的集合。类似于二维平面（直线），这里 $a,b,c$ 定义了平面的方向，$d$ 定义了平面相对于原点的偏移量。 偏移量不同的平面 法向量 $\boldsymbol n=(a,b,c)$ 是一个垂直于平面 $ax+by+cz=d$ 的向量，因此常用于描述平面的方向。 关于…

点和向量 叉积 与二维向量叉积不同，三维向量叉积是一个向量，向量 $\boldsymbol a=(x1,y1,z1)$ 叉乘 $\boldsymbol b=(x2,y2,z2)$ 的计算公式如下 $$\begin{aligned}(x1,y1,z1)\times (x2,y2,z2) &= \det \begin{bmatrix}\bold…

B-spline Cox-de Boor recursion formula 定义集合 $U$ 由 $m+1$ 个不降的实数 $u_0\le u_1\le\cdots\le u_m$ 构成，我们称 $u_i$ 为结点（knot），$U$ 为结点向量（knot vector）。 给定结点向量 $U$，则其对应的 $k$ 次B-spline $N_{i…

周期为 $2\pi$ 的傅里叶级数 傅里叶级数是一种利用三角函数近似周期函数的方法，本节将以周期为 $2\pi$ 的函数 $f(x)$ 为例，解析傅里叶级数是如何做到拟合的： $$f(x) = a_0 + \sum_{i=1}^{\infty} a_i\cos ix + \sum_{j=1}^{\infty}b_j\sin jx$$ 一个分别采用傅…

可分离变量的微分方程 形如 $y^\prime = f(x)g(y)$ 的微分方程被称为是可分离变量的微分方程，这类方程的求解思路非常简单，如下： $$\begin{aligned}y^\prime = f(x)g(y) &\Rightarrow \frac{\mathrm{d}y}{g(y)}=f(x)\mathrm{d}x\\&…

注意，本文的主要内容是《算法导论》书中的KMP算法，而非原始论文给出的形式。相比较于原始论文，算法导论中给出的border形式的KMP算法更加实用，原因是XCPC竞赛中border的作用远超过模式匹配，因此本文中的next数组定义为前缀子串最长的border。 如果你是考研选手，请查阅文末的原始论文定义！！！ Border 先定义两个符号： 字符串…

树状数组实例 一般情况下，数据结构我们都以 $1$ 作为起始下标。 lowbit $lowbit$ 操作是为了求出一个数字 $x$ 在二进制形态下，最低位的 $1$ 。 例如 $(110100)_2$ 中最低位 $1$ 的是 $(100)_2$ 。 $lowbit$ 求解的方法是，先将 $x$ 的二进制按位取反，然后 $+1$ ，再按位与原数字。 …