2-1_Finding Roots of Equations (1-Bisection Method)
Problem StatementGiven some functions $f(x)$, determine the value(s) of x where $f(x) = 0$Especially when $f(x)$ is not analytically.Root finding algorithmsTwo main types:Bracketing MethodsOpen MethodsFollowing steps are essential for any root find algorithms:Guess: one more more initial values for $x$Iterate: using the scheme to improve the guessCheck the convergenceBracketing methodPut it simply, it a kind of method like binary search. We can test if $f(a)f(b) < 0$ to determine whether we need to discard half of the interval.The approximation relative error is$$ \epsilon_r = \frac{x_{i+1} - x_i}{x_{i+1}} $$When $|\epsilon_r|$ becomes less than a specified threshold $\epsilon_s$ the iterations are stopped.For this algorithms, we are able to set the iteration number $n$. The absolute value of error $|E| = |V_t - V_a|$. Let $L = b- a$ be the length of the interval, so we know the interval length after $n$ iteration his $\frac{L}{2^n}$Therefore,$$ |E| \leq \frac{L}{2^n} $$So we can determine the iteration number $n$ as:$$ n = \frac{\ln \frac{L}{E_{max}}}{\ln 2} $$ImprovementTo improve the root position estimation, we can construct a straight line between point $a, b$, and then use the intersection point with x axis as the initial point.As shown in the figure,$$ x_i = b - f(b) \frac{b-a}{f(b)-f(a)} $$
Pre-requisite KnowledgeRolle's theoremLet $f:[a, b] \to \mathbb{R}$ be differentiable. Assume that $f(a) = f(b)$, then there is at least one point $c \in (a, b)$ where $f'(c) = 0$Mean value theoremLet $f:[a, b] \to \mathbb{R}$ be differentiable. Then there is at least one point $c \in (a, b)$ such that $f'(c) = \frac{f(b) - f(a)}{b - a}$Taylor theoremTaylor's theorem is a fundamental result in calculus that provides a way to approximate a function by its Taylor series, which is an infinite sum of terms calculated from the values of the function's derivatives at a single point.Statement of Taylor's Theorem:For a function $ f(x) $ that is $ n $ times differentiable at a point $ a $, Taylor's theorem states that the function can be approximated near $ a $ by the $ n $th-order Taylor polynomial plus a remainder term.The Taylor polynomial $ P_n(x) $ of $ f(x) $ centered at $ a $ is given by:$$ P_n(x) = f(a) + f'(a)(x - a) + \frac{f''(a)}{2!}(x - a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x - a)^n $$The remainder term $ R_n(x) $ represents the error in approximating $ f(x) $ by $ P_n(x) $.Remainder Term:There are several forms of the remainder term, including the Lagrange form and the Peano form.The Lagrange form of the remainder is often used and is given by:$$ R_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}(x - a)^{n+1} $$where $ \xi$ is some point between $ a $ and $ x $.Therefore, the error is given by:$$ E = f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} (x - a)^{n+1} $$with the upper bound$$ |E| \leq \max_{\xi \in [a,x]} \frac{|f^{(n+1)}(\xi)|}{(n+1)!} (x-a)^{n+1} $$We can note that：$$ f(x) = P_n(x) + O(h^{n+1}), h = (x-a) $$This is also called the truncation error.Approximating Continuous FunctionsLet $f:[a, b] \to \mathbb{R}$ be differentiable. The Stone-Weierstrass Theorem states that for any small number $\epsilon > 0: \exists P(x)$ a polynomial function such that：$$ \max_{x \in [a, b]} |f(x) - P(x)| \leq \epsilon $$
DefinitionWe define the error as:$$E = V_t - V_a$$where $V_t$ is the ground truth value and $V_a$ is our approximation valueThe definition of Relative error, which is normalized error of $E$ by $V_t$:$$E_r = \frac{E}{V_t}$$If $\epsilon$ is an approximation for the error, then the relative approximate error $\epsilon_r$ is defined as:$\epsilon_r = \frac{\epsilon}{V_a}$ExampleIf we use $\frac{22}{7}$ as an approximation of $\pi$$E = \pi - \frac{22}{7}$ $E_r = \frac{E}{\pi} \approx -0.04\%$$\epsilon_r = \frac{\pi - \frac{22}{7}}{\frac{22}{7}} \approx -0.04\%$
Zero-Level Set"Zero-level set"（零级集）是数学和几何学中的一个术语，特别是在描述隐式曲面或隐式函数时常用到。在三维空间中，隐式函数通常表示为 $f(\mathbf{x}) = 0$，其中 $\mathbf{x} $ 是空间中的点。这个等式定义了一个曲面或者一个空间中的某种几何体，称为零级集。换句话说，零级集是满足隐式函数 $ f(\mathbf{x}) = 0 $ 的所有点构成的集合，它们组成了隐式函数定义的曲面或边界。例如，在有符号距离函数（Signed Distance Function，SDF）中，零级集表示所有距离函数值为零的点的集合，这些点恰好位于表面上。在几何建模和计算机图形学中，零级集常用于表示曲面的边界或界面，因为它提供了一种便捷的方式来隐式表示和处理复杂的几何结构。
Discretization process for State Space Model of Mamba
DefinitionIn Mamba, we have the formula:$$ h'(t)=Ah(t) + Bx(t) $$Here, $A, B$ represent the parametric matrix, and $h$ represents the hidden state, and $x$ represents the input.It is basically from control theory, which is originally:$x'(t) = Ax(t) + Bu(t)$Here we inherit the initial statement of the state space theory, where $x$ represent the hidden state, and $u$ represents the input at this time step.MotivationBy observation, we will realize that:$x'(t) = Ax(t)$which reminds us the $(e^x)' = e^x$.This is where the discretization process from.Move the $Ax(t)$ to the LHS,$$ x'(t) - Ax(t) = Bu(t) $$Let it be:$e^{-At} x'(t) - e^{-At}x(t) = e^{-At} Bu(t)$Note that $F(t) = e^{-At}x(t)$, then $F'(t) = -Ae^{-At}x(t) + e^{-At} x'(t)$Also we know that $F'(t) = e^{-At}Bu(t)$Through the integration, we can get a formular which contains both $u$ and $x$:$$ \forall \lambda \in (-\infty, +\infty), F(t) = F(\lambda) + \int_{\lambda}^{t} F'(\tau) \mathrm{d}\tau $$Specificly, for the convinience, let $\lambda = 0$, substitute $F(t) = e^{-At}x(t)$ and $F'(t)$ into the above equation$$ e^{-At}x(t) = x(0) + \int_{0}^{t} -Ae^{-A\tau}x(\tau) + e^{-A\tau}x(\tau) \mathrm{d} \tau $$It also equals to:$$ e^{-At}x(t) = x(0) + \int_{0}^{t} e^{-A\tau} Bu(\tau) \mathrm{d} \tau $$Divide both sides by $e^{-At}$$$ x(t) = e^{At}x(0) + e^{At}\int_{0}^{t} e^{A\tau} Bu(\tau) \mathrm{d} \tau $$Generally,$$ x(t_k) = e^{At_k} x(0) + e^{At_k} \int_{0}^{t_k} e^{-A\tau} Bu(\tau) \mathrm{d} \tau $$To get the form like $x(t_{k+1}) = ?? x(t_k)$$x(t_{k+1}) = e^{A(t_k + (t_{k+1}-t_k))}x(0) + e^{A(t_k + (t_{k+1} - t_k))} \int_{0}^{t_{k+1}} e^{-A\tau} Bu(\tau) \mathrm{d} \tau$Get the simplication,$$ x(t_{k+1}) = e^{A(t_{k+1} - t_k)} [e^{At_k}x(0) + e^{At_k} \int_{0}^{t_k} -e^{A\tau} Bu(\tau) \mathrm{d}\tau] + e^{At_{k+1}} \int_{t_k}^{t_{k+1}} e^{-A\tau} bu(\tau) \mathrm{d} \tau $$Notice that, the term in $[]$ equals to $x(t_k)$. Hence, it is equivalent to:$$ x(t_{k+1}) = e^{t_{k+1} - t_k} x(t_k) + \int_{t_k}^{t_{k+1}} e^{A(t_{k+1} - \tau)} bu(\tau) \mathrm{d} \tau $$Zero-Order HolderHere we introduce the Zero-Order Holder. Superficially, we only focus the key step from which is zero-order holder, rather than detailed zero-order holder theory.Note the $T = t_{k+1} - t_k$. Let $T \to 0$By zero-order holder, we regard $u(\tau)$ as $u(t_k)$. Therefore,$$ x(t_{k+1}) = e^{AT}x(t_k) + \int_{t_k}^{t_{k+1}} e^{A(t_{k+1} - \tau)} Bu(t_k) \mathrm{d} \tau $$The second term of RHS is equivalent to:$$ e^{At_{k+1}} Bu(t_k) \int_{t_k}^{t_{k+1}} e^{-A\tau} \mathrm{d} \tau =e^{At_{k+1}} Bu(t_k) [ -\frac{1}{A} (e^{-At_{k+1}} - e^{-At_k})] $$Get the simplication:$$ \Rightarrow Bu(t_k) \times \frac{1}{A} [e^{A(t_{k+1} - t_k)}- 1] $$Substitute back to the above equation:$$ x(t_{k+1}) = e^{AT}x(t_k) + Bu(t_k) \times \frac{1}{A} [e^{AT} - I] $$We substitute $1$ by the identity matrix $I$, because all of our computations at here are based on matrix operations.Notice that $T \to 0$ is equivalent to a standard infinitesimal $\Delta$. Therefore, we substitute all the $T \to 0$ by $\Delta$$$ x(t_{k+1}) = e^{A\Delta}x(t_k) + Bu(t_k) \cdot \frac{\Delta (e^{AT} - I)}{\Delta A} $$$$ x(t_{k+1}) = e^{A\Delta} x(t_k) + \Delta Bu(t_k) (e^{AT} - I) (\Delta A)^{-1} $$ResultDon't forget that our target is that $x(t_{k+1}) = \overline{A} x(t_k) + \overline{B} u(t_k)$, where $\overline{A} $ and $\overline{B}$ are both parametric matrices.Here we can get$$ \overline{A} = e^{\Delta A} $$$$ \overline{B} = (\Delta A)^{-1} (e^{\Delta A} - I) \Delta B $$However, $h(t_{k+1}) = \overline{A} h(t_k) + \overline{B} x(t_{k+1})$. This is because of the definition of $h$, where $h_0 = \overline{B} x_0$In the control theory, $x_1$ is from $x_0$ and $u_0$In the SSM, $h_1$ is from hidden state $h_0$. Because the input $x_0$ corresponding $u_0$ which corresponds to hidden state $x_0$ in the control theory, $h_1$ is from input $x_1$.
VectorCross Product叉积，简单回顾一下$$ ||\vec{a} \times \vec{b}|| = ||a||||b|| \sin \phi $$而 $\vec{a} \times \vec{b}$ 的方向可以用右手系来判断。在笛卡尔坐标系中，其结果可以用：$$ \vec{a} \times \vec{b} = (y_az_b - z_ay_b, z_ax_b - x_az_b, x_ay_b - y_ax_b) $$Orthonormal BasesConstructing a Basis from a Single Vector利用单个向量构造正交基首先取该向量的方向向量：$$ \vec{w} = \frac{\vec{a}}{||\vec{a}||} $$之后选取任意一个与 $\vec{w}$ 不共线的向量 $\vec{t}$，利用叉积来构造与 $\vec{w}$ 正交的单位向量$$ \vec{u} = \frac{\vec{t} \times \vec{w}}{||\vec{t} \times \vec{w}||} $$Constructing a Basis from a Single Vector将 $\vec{u}$ 构造中的 $\vec{t}$ 替换成第二个向量 $\vec{b}$ 即可。Curves and Surfaces2D Implicit Curves一种常见的描述二维曲线的方法是隐等式（Implicit Equation）。二维曲线的一般形式是：$$ f(x,y) = 0 $$其中， 点 $(x,y)$ 是 $f(x,y)=0$ 的根，表示该点在曲线上。反之则不在。例如，一个圆可以表示为 $f(x,y) = (x-x_c)^2 + (y - y_c)^2 -r^2$ 。因为在曲线上的点并非显式地表达出来，而是要解这个等式，所以成为 Implicit Equation。此外，我们还可以用向量来压缩我们的表达式。如果我们有 $\vec{c} = (x_c, y_c)$ 和 $\vec{p} = (x,y)$，那么以 $(x_c, y_c)$ 为圆心 $r$ 为半径的原则可以用这些满足以下条件的位置向量来表示：$$ (\vec{p} - \vec{c}) \cdot (\vec{p} - \vec{c}) - r^2 = 0 $$由点积的性质可知，该式也等价于：$$ \vert \vert \vec{p} - \vec{c} || -r^2 = 0 $$2D Gradient这一节我们讨论2D梯度假如我们认为 $f(x,y)$ 是一块高地且高度$=f(x,y)$，那么梯度向量指向的是最大向上斜率的方向。梯度向量 $\nabla f(x,y)$ 由下式给出：$$ \nabla f(x,y) = (\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}) $$在一个在隐曲线 $f(x,y) = 0$ 上的点测量的梯度向量是与 tangent vector 在该点垂直的一个向量。这个垂直的向量通常称为 normal vector （法向量）。因为梯度向量指向的是最大向上斜率的方向，这说明了梯度向量指向了 $f(x,y) > 0$ 的区域。3D Implicit Surfaces类似于 2D 的情形，我们可以简单给出 3D Implicit Equation 来描述一个 3D 平面$$ f(x,y,z) = 0 $$同理，可以用向量来表示。有 $\vec{p} =(x,y,z)$ ，上式可以重写为：$$ f(\vec{p}) = 0 $$Surface Normal to an Implicit SurfaceSurface Normal，即法线。其目的是为了减小计算量，是一个垂直于平面的向量。任意一个在平面上的点都有可能有不同的法向量。类似地，梯度为2D隐曲线指出了一条法线，在点 $\vec{p}$ 处的3D平面发现由隐函数的梯度给出：$$ \vec{n} = \nabla f(\vec{p}) = (\frac{\partial f(\vec{p}}{\partial x}, \frac{\partial f(\vec{p})}{\partial y}, \frac{\partial f(\vec{p})}{\partial z}) $$Implicit Planes上面提到了法线。我们是否可以用法线来定义一个平面？假如我们有一个无限平面，穿过点 $\vec{a}$，且在该点有法线 $\vec{n}$。则该平面的 Implicit Equation 可以表达为：$$ (\vec{p} - \vec{a}) \cdot \vec{n} = 0 $$其中 $\vec{p}$ 是一个任意的在平面上的点。这个等式实际上是在描述：一个从 $\vec{a}$ 到 $\vec{p}$ 的向量是垂直于平面法线 $n$ 的。如果 $\vec{p}$ 不在该平面内，则该等式不成立。有时候我们需要找到一个包含点 $\vec{a}, \vec{b}, \vec{c}$ 的平面。该平面的法线可以用该平面内的任意两个向量的叉积给出：$$ \vec{n} = (\vec{b} - \vec{a})\times (\vec{c} - \vec{a}) $$利用上式，可以重写本节的第一个式子：$$ (\vec{p} - \vec{a}) \cdot ((\vec{b} - \vec{a}) \times (\vec{c} - \vec{a})) = 0 $$该式可以这么理解：由 $\vec{p} - \vec{a}$ , $\vec{b} - \vec{a}$ 和 $\vec{c} - \vec{a}$ 定义的平行管的体积为 $0$，即他们是共面的。一个 Full-Brown 的笛卡尔表示由行列式给出：$$ \begin{Vmatrix} x - x_a & y - y_a & z - z_a \\ x_b - x_a & y_b - y_a & z_b - z_a \\ x_c-x_a & y_c - y_a & z_c-z_a\end{Vmatrix} = 0 $$本质上，上两式是等价的。且两者都容易用来进行编程。3D Quadric Surfaces类似于二次多项式可以用来定义2D中的二次曲线，由 $x,y,z$ 组成的二次多项式可以用来在 3D 中定义二次平面。例如，一个球可以表示成：$$ f(\vec{p}) = (\vec{p} - \vec{c})^2 - r^2= 0 $$一个在固定在轴上的椭球可以如下表示：$$ f(\vec{p}) = \frac{(x-x_c)^2}{a^2} + \frac{(y-y_c)^2}{b^2} + \frac{(z-z_c)^2}{c^2} - 1 = 0 $$3D Curves from Implicit Surfaces根据3D Implicit Surface 的启发，3D implicit curve 是否可以用 $f(\vec{p}) = 0$ 来描述呢？答案是可以的。但是所有这些曲线都只是退化曲面 (Degenerate Surface)，在实践中很少有用。Degenerate Surface 就是会在一条线或者一个点上坍缩的一个平面。其实由定义可以联想到这一性质。一条 3D 曲线可以由两个 Implicit equations 的节点同时构造出来：$$ f(\vec{p}) = 0, g(\vec{p}) = 0 $$例如，一条 3D Curves 可以由它截的两个平面来表示。一种更简便的方法是用参数式来表示。2D Parametric Curves一个用参数来描述的曲线，使用单参数来控制的。这个参数可以被视为一种在曲线上连续的索引。这样的曲线可以由这种形式来表示：$$ \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} g(t) \\ h(t) \end{bmatrix} $$该式中，$(x,y)$ 是在曲线上的一个点。$t$ 是一个影响这条曲线的一个参数。对于一个给定的 $t$，一些点是由函数 $g$ 和 $h$ 来决定的。对于连续的 $g$ 和 $h$，$t$ 的微小变化就会体现在 $x,y$ 的微笑变化中。所以，当 $t$ 连续的变化的时候，$(x,y)$ 也连续的被勾勒出来。这是一种很好的特性，因为我们可以用参数 $t$ 来显式地构造在曲线上的点。通常，我们可以用向量的形式来写一个参数式的曲线：$$ \vec{p} = f(t) $$其中，$f$ 是一个 vector-valued 的函数， $f: \mathbb{R} \rightarrow \mathbb{R}^2$。2D Parameter Lines一条经过 $\vec{p_0} =(x_0, y_0)$ 和 $\vec{p_1} = (x_1, y_1)$ 的点可以写做：$$ \begin{bmatrix} x \\ y\end{bmatrix} = \begin{bmatrix} x_0 + t(x_1-x_0) \\ y_0 + t(y_1-y_0)\end{bmatrix} $$上式中， $x, y$ 给出的形式非常类似，我们可以用一个更简单的向量形式来表达。对于 $\vec{p} = (x,y)$:$$ \vec{p}(t) = \vec{p_0} + t(\vec{p_1 - \vec{p_0}}) $$另外一种只用一个点 $\vec{o}$ 和一个向量 $\vec{d}$ 的表达方式是：$$ \vec{p}(t) = \vec{o} + t(\vec{d}) $$当向量 $\vec{d}$ 的模长为单位长度时，这条线被称作 arc-length parameterized （弧长参数化）的。这指出，参数 $t$ 就是这条线上长度的。任何参数式的曲线都可以被弧长参数化。弧长参数化式显然是一种非常方便的形式。2D Parametric Curves圆心在 $(x_c, y_c)$ 半径为 $r$ 的圆有参数式：$$ \begin{bmatrix} x \\ y\end{bmatrix} = \begin{bmatrix} x_c+r\cos \phi \\ y_c + r \sin \phi \end{bmatrix} $$为了保证参数 $\phi$ 是一个独特的参数，对于每一个在曲线上的点，我们可以限制其定义域 $\phi \in [0,2\pi)$ 或者 $\phi \in (-\pi, \pi]$。一个轴在坐标轴上的椭圆可以用不同的尺寸的 $x,y$ 来构造参数等式来表达：$$ \begin{bmatrix} x \\ y\end{bmatrix} = \begin{bmatrix} x_c+a \cos \phi \\ y_c + b\sin\phi \end{bmatrix} $$3D Parametric Curves类似于 2D 的情况，3D Parametric Curves 可以表示为：$$ x = f(t), y = g(t), z=h(t) $$例如，一个围着 $z$ 轴的螺旋状曲线可以写作：$$ x = \cos t, y = \sin t, z = t $$同理，如果我们要控制曲线的起点和终点，函数 $f,g,h$ 定义在 $D \subset \mathbb{R}$ 。其向量形式可以写作：$$ \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \vec{p(t)} $$3D Parametric Lines不多细说，跟 2D 情况类似。3D Parametric Surfaces参数化方法可以用来定义 3D 空间中的平面，类似于我们如何定义曲线。在 3D 中平面的形式是：$$ x = f(u,v), y = g(u,v), z = h(u,v) $$或者，向量形式是：$$ \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \vec{p}(u,v) $$例如，一个在地球上的点可以用经度和纬度来描述。如果我们定义地球的原点就是地心的话，设 $r$ 是地球的半径，一个在原点球的坐标系就可以用来帮助我们表示 Parametric equations:$$ x = r \cos \phi \sin \theta, y = r \sin \phi \sin \theta, z = r\cos \theta $$我们也可以写成向量形式，但是这并不为这样特定的参数形式具备可行性。我们想要对于一组给定的 $(x,y,z)$ 寻找一对 $(\theta, \phi)$。如果我们假设 $\phi \in (-\pi, \pi]$，这可以很轻松的用 $\arctan2$ 函数(atan2函数)来实现：$$ \theta = \arccos(z / \sqrt{x^2 + y^2 + z^2}), \phi = \arctan2(y,x) $$结合 Implicit surfaces，函数 $f$ 的微分给出了该平面的法向量，同时 $\vec{p}$ 的微分也告诉了我们该平面的几何信息。考虑函数 $\vec{q}(t) = \vec{p}(t,v_0)$。这个函数定义了一个 Parametric curve ，通过变化 $u$ 在保持$v = v_0$ 不变的时候。这条曲线被称为在平面中的 Isoparametric curve (等参数曲线)。$\vec{q}$ 的微分给出了一个与曲线相切的向量。并且由于这条曲线在平面内，$\vec{q'}$ 也在平面内。因为这是通过变化 $\vec{p}$ 中的参数来得到的，所以 $\vec{q'}$ 是 $\vec{p}$ 关于 $u$ 的偏微分，我们记作 $\vec{p_u}$。类似的说法展示了偏微分 $\vec{p_u}$ 给出了等参数曲线的切线，对于常数 $u$。这也是平面的第二个相切向量。由上，$\vec{p}$ 的微分给出了平面上任意一点的两个相切向量。平面的法线可以通过这些向量的叉积得到：因为他们二者都与平面相切，他们的叉积则与他们正交。这样就是平面的法线。右手系给出了一种方法哪一个是前面，或者说是外面，对于某一个平面。我们将用向量方便地表示：$$ \vec{n} = \vec{p_u} \times \vec{p_v} $$该法向量指向平面外方向。Summary for Curves and Surfaces2D 中的 Implicit curves 和 3D 中的 Implicit surfaces 用一个 scalar-valued （一个标量来衡量）的二元或者三元函数来表示：$f: \mathbb{R}^2 \to \mathbb{R}$ 或者 $f: \mathbb{R}^3 \to \mathbb{R}$ ，并且包含所有满足函数值为 $0$ 的点：$$ S = \{ \vec{p} | f(\vec{p}) = 0 \} $$2D 或者 3D 中的参数化曲线使用 vector-valued （一个矢量来衡量）的单变量函数来衡量：$\vec{p}: D \subset \mathbb{R} \to \mathbb{R}^2$ 或者 $\vec{p}: D \subset \mathbb{R} \to \mathbb{R}^3$ ，并且曲线扫过所有地方随着 $t$ 在整个 $D$ 上变化：$$ S = \{ \vec{p}(t) | t \in D \} $$3D 中的参数化平面也是用 vector-valued 的二元函数来表示的：$\vec{p}: D \subset \mathbb{R^2} \to \mathbb{R^3}$，该平面包括所有点 $(u,v)$ 在定义域内：$$ S = \{\vec{p}(t)| (u,v) \in D \} $$对于 Implicit curves 和 Implicit surfaces，法向量由 $f$ 的微分给出（即梯度）。相切向量（对于一条曲线）或者一组相切向量（对于一个平面）可以用法线的微分来构造一组基底。对于参数化曲线和平面，$\vec{p}$ 的微分给出了相切向量（对于一条曲线）或者一组相切向量（对于一个平面），并且法向量可以通过构造一组基底从任何切线中得出。
定义对于两个序列 $a_1 \geq a_2 \geq \dots \geq a_n$ 和 $b_1 \geq b_2 \geq \dots \geq b_n$，则有不等式：$\sum\limits_{i=1}^{n} a_ib_i\geq \sum\limits_{i=1}^{n} a_ib_{\pi(i)} \geq \sum\limits_{i=1}^{n} a_1b_{n-i+1}$其中 $\pi(i)$ 是任意一个 $n$ 阶排列。证明假如排列 $\pi(i)$ 使 $\sum\limits_{i=1}^{n} a_{i}b_{\pi(i)}$ 最大，那么 $\pi(i)$ 是一个确定的排列即 $\forall i, \pi(i) = i$。假设该结论不成立，那么 $\pi(i)$ 为一个乱序 $n$ 阶排列且 $\exists i, \pi(i) \neq i$，设 $i$ 是排列 $\pi$ 的第一个出现 $\pi(i) \neq i$ 的位置。$i$ 是第一个这样的位置，那么 $\pi(i) = j > i$，并且一定存在一个 $k >i$ 有 $\pi(k) = i$。因为 $i<j$ 那么 $b_i \geq b_j$，同时有：因为 $i < k$，那么 $a_i \geq a_k$。因此：$$ (a_k - a_j)(b_j - b_i) \geq 0 \Longrightarrow a_ib_i + a_jb_j \geq a_ib_j + a_jb_i $$所以通过使 $\pi(i) = j, \pi(k) = i$ 变成 $\pi(i) = i, \pi(j) = j$， $\sum\limits_{i=1}^{n} a_ib_{\pi(i)}$ 单调不减。证毕。
LinkDescription要求： $x^2 - y = z^2$, 满足 $1 \leq x, y \leq N, N \leq 10^{12}$Sol移项可得：$x^2 - z^2 = y$ ，利用平法差公式：$(x+z)(x-z) = y$令 $p = (x+z), q = (x-z)$，因为 $x, y, z \in Z$，所以 $p \geq q$，现在要求 $pq = y$，可以枚举 $q$，然后 $O(1)$ 计算合法的 $p$ 的个数。注意范围：$q \leq p \leq \frac{N}{q}, p \equiv q \mod {2}$Code#include <bits/stdc++.h> #define int long long using namespace std; signed main() { int n, ans = 0; cin >> n; const int mod = 998244353; for (int i = 1, l, r; i * i <= n; ++ i) { l = min(i, n / i), r = max(i, n / i); ans = (ans + ((r - l) / 2ll + 1) % mod) % mod; } printf("%lld\n", ans); return 0; }
LinkSol先对给你的这个数组排序，我们设排完序后的数组为$a[1],a[2],\dots,a[n]$，给你的数组升序排序后是$b[1],b[2],\dots,b[n * (n-1) /2]$考虑$b[1]$是怎么被$a[]$相加而得的，因为$b[1]$是$b$中最小的元素，那么$b[1]=a[1]+a[2]$第二小的$b[2]=a[1] + a[3]$由$a[2]$开始往后相加的元素一定在$b[x] = a[1]+a[k]$开始，这样的$b[x]$我们只需要$O(n)$的枚举找到就可以了做法就出来了每次找到$a[k]$这个元素，把$a[1]+a[2], a[1]+a[3],\dots,a[1]+a[k]$这些元素找出来，再把他们在$b$中去掉，再从$a[2]$开始，以此类推时间复杂度$O(n^3)$Code#include <bits/stdc++.h> using namespace std; #define int long long const int SIZE = 1e7 + 5; int n, m, cnt; int a[SIZE], b[SIZE]; std::multiset < int > s; std::vector < vector < int > > ans; inline int read() { char ch = getchar(); int f = 1, x = 0; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * f; } inline void solve(int p) { if ((a[1] + a[2] + a[p]) & 1) return; b[1] = (a[1] + a[2] + a[p]) / 2 - a[p]; b[2] = a[1] - b[1], b[3] = a[2] - b[1]; if (b[1] <= 0) return; s.clear(); for (int i = 3; i <= m; ++ i) { if (i != p) s.insert(a[i]); } for (int i = 4; i <= n; ++ i) { b[i] = *s.begin() - b[1]; s.erase(s.begin()); for (int j = 2; j < i; ++ j) { auto it = s.find(b[i] + b[j]); if (it == s.end()) return; s.erase(it); } } std::vector < int > tmp; for (int i = 1; i <= n; ++ i) tmp.push_back(b[i]); ans.push_back(tmp); return; } inline int cmp(vector < int > &a, vector < int > &b) { for (int i = 0; i < n; i++) { if (a[i] == b[i]) continue; return a[i] > b[i]; } } signed main() { while (std::cin >> n) { m = n * (n - 1) / 2; for (int i = 1; i <= m; ++ i) a[i] = read(); std::sort(a + 1, a + m + 1); for (int i = 3; i <= m; ++ i) { if (i == 3 || a[i] != a[i - 1]) solve(i); } if (!ans.size()) { ans.clear(); puts("Impossible"); continue; } std::sort(ans.begin(), ans.end(), cmp); for (int i = 0; i < ans.size(); ++ i) { for (int j = 0; j < n; ++ j) printf("%d ", ans[i][j]); puts(""); } ans.clear(); } return 0; }