From 72c6b47419d38d1afa18c9e1bee467966ab50b0e Mon Sep 17 00:00:00 2001 From: Ir1d Date: Fri, 23 Nov 2018 09:58:14 +0800 Subject: [PATCH] fix: --- docs/geometry/2d.md | 4 ++-- docs/math/bezouts.md | 2 +- docs/math/complex.md | 27 ++++++++++++++------------- docs/math/crt.md | 4 ++-- docs/math/mobius.md | 12 ++++++------ docs/string/prefix-function.md | 16 ++++++++-------- 6 files changed, 33 insertions(+), 32 deletions(-) diff --git a/docs/geometry/2d.md b/docs/geometry/2d.md index ff5b7778..112215c3 100644 --- a/docs/geometry/2d.md +++ b/docs/geometry/2d.md @@ -84,11 +84,11 @@ $$ 在三角形 $\triangle \text{ABC}$ 中，若角 $A,B,C$ 所对边分别为 $a,b,c$，则有： $$ -\begin{align} +\begin{aligned} a^2&=b^2+c^2-2bc\cos A\\ b^2&=a^2+c^2-2ac\cos B\\ c^2&=a^2+b^2-2ab\cos C -\end{align} +\end{aligned} $$ 上述公式的证明略。均为人教版高中数学 A 版必修五内容。 diff --git a/docs/math/bezouts.md b/docs/math/bezouts.md index b91c3b0f..126f150a 100644 --- a/docs/math/bezouts.md +++ b/docs/math/bezouts.md @@ -21,7 +21,7 @@ 转证 $a_1x+b_1y=1$. 由带余除法: $$ - \begin{align*}a_1 &= q_1b+r_1 &(0\leq r_1 哇哦我们定义的数的性质这么好！ @@ -34,11 +34,12 @@ ![](./images/complex-1.png) -​
图片来自：人教版高中数学 A 版选修 2-2 第 103 页
+
图片来自：人教版高中数学 A +版选修 2-2 第 103 页
-## 2. 复数的性质与运算 +## 复数的性质与运算 -### 2.1. 复数的几何意义 +### 复数的几何意义 我们知道了 $a+b\text{i}$ 这样类似的形式的数被称为复数，并且给出了定义和分类，我们还可以挖掘一下更深层的性质。 @@ -60,9 +61,9 @@ 并且由向量的知识我们发现，虚数不可以比较大小（但是实数是可以的）。 -### 2.2. 复数的运算 +### 复数的运算 -#### 2.2.1 复数的加法与减法 +#### 复数的加法与减法 我们规定，复数的加法规则如下： @@ -91,18 +92,18 @@ $$ 这同样符合向量的减法运算。 -#### 2.2. 复数的乘法与除法 +#### 复数的乘法与除法 我们规定，复数的加法规则如下： 设 $z_1=a+b\text{i},z_2=c+d\text{i}$，那么 $$ -\begin{align} +\begin{aligned} z_1z_2&=(a+b\text{i})(c+d\text{i})\\ &=ac+bc\text{i}+ad\text{i}+bd\text{i}^2\\ &=(ac-bd)+(bc+ad)\text{i} -\end{align} +\end{aligned} $$ 可以看出，两个复数相乘类似于两个多项式相乘，只需要把 $\text{i}^2$ 换成 $-1$，并将实部与虚部分别合并即可。 @@ -124,10 +125,10 @@ $$ 除法运算是乘法运算的逆运算，我们可以推导一下： $$ -\begin{align} +\begin{aligned} \frac{a+b\text{i}}{c+d\text{i}}&=\frac{(a+b\text{i})(c-d\text{i})}{(c+d\text{i})(c-d\text{i})}\\ &=\frac{ac+bd}{c^2+d^2}+\frac{bc-ad}{c^2+d^2}\text{i} &(c+d\text{i}\not =0) -\end{align} +\end{aligned} $$ 为了分母实数化，我们乘了一个 $c-d\text{i}$，这个式子很有意义。 diff --git a/docs/math/crt.md b/docs/math/crt.md index f2e0ab1b..7b63e32b 100644 --- a/docs/math/crt.md +++ b/docs/math/crt.md @@ -117,13 +117,13 @@ $x=b_1+b_2n_1+b_3n_1n_2...+b_kn_1n_2...n_{k-1} ,b_i\in [0,n_i)$ 转化方法考虑依次对 PMR 取模 $$ -\begin{align} +\begin{aligned} b_1&=a_1 \mod n_1\\ b_2&=(a_2-b_1)c_{1,2} \mod n_2\\ b_3&=((a_3-b_1')c_{1,3}-x_2')c_{2,3} \mod n_3\\ &...\\ b_k&=(...((a_k-b_1)c_{1,k}-b_2)c_{2,k})-...)c_{k-1,k} \mod n_k -\end{align} +\end{aligned} $$ 其中$c_{i,j}$表示$n_i$对$n_j$的逆元,$c_{i,j}n_i=1 \mod n_j$ diff --git a/docs/math/mobius.md b/docs/math/mobius.md index f5f484ec..5965f031 100644 --- a/docs/math/mobius.md +++ b/docs/math/mobius.md @@ -17,12 +17,12 @@ 若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也为积性函数： $$ -\begin{align*} +\begin{aligned} h(x)&=f(x^p)\\ h(x)&=f^p(x)\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g(\frac{x}{d}) -\end{align*} +\end{aligned} $$ ### 例子 @@ -63,12 +63,12 @@ $\text{Dirichlet}$ 卷积满足交换律和结合律。 ### 例子 $$ -\begin{align*} +\begin{aligned} \varepsilon=\mu*1&\Leftrightarrow\varepsilon(n)=\sum_{d\mid n}\mu(d)\\ d=1*1&\Leftrightarrow d(n)=\sum_{d\mid n}1\\ \sigma=d*1&\Leftrightarrow\varepsilon(n)=\sum_{d\mid n}d\\ \varphi=\mu*\text{ID}&\Leftrightarrow\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) -\end{align*} +\end{aligned} $$ * * * @@ -158,13 +158,13 @@ $$ 易知如下过程： $$ -\begin{align*} +\begin{aligned} \varphi*1&=\sum_{d\mid n}\varphi(\frac{n}{d})\\ &=\sum_{i=0}^c\varphi(p^i)\\ &=1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1)\\ &=p^c\\ &=\text{ID}\\ -\end{align*} +\end{aligned} $$ 该式子两侧同时卷 $\mu$ 可得 $\displaystyle\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})$ diff --git a/docs/string/prefix-function.md b/docs/string/prefix-function.md index 08c1b2bd..6b4e375c 100644 --- a/docs/string/prefix-function.md +++ b/docs/string/prefix-function.md @@ -168,10 +168,10 @@ for (int i = 0; i <= n; i++) ans[i]++; 现在假设 $n$ 不可以被 $k$ 整除，我们将通过反证法证明这意味着答案为 $n$[^1]。假设其最小压缩表示 $r$ 的长度为 $p$（$p$ 整除 $n$），字符串 $s$ 被划分为 $n / p \ge 2$ 块。那么前缀函数的最后一个值 $\pi[n - 1]$ 必定大于 $n - p$（如果等于则 $n$ 可被 $k$ 整除），也即其所表示的后缀将部分的覆盖第一个块。现在考虑字符串的第二个块。该块有两种解释：第一种为 $r_0 r_1 \dots r_{p - 1}$，另一种为 $r_{p - k} r_{p - k + 1} \dots r_{p - 1} r_0 r_1 \dots r_{p - k - 1}$ 。由于两种解释对应同一个字符串，因此可得到 $p$ 个方程组成的方程组，该方程组可简写为 $r_{(i + k) \bmod p} = r_{i \bmod p}$，其中 $\cdot \bmod p$ 表示模 $p$ 意义下的最小非负剩余。 $$ -\begin{gather} +\begin{gathered} \overbrace{r_0 ~ r_1 ~ r_2 ~ r_3 ~ r_4 ~ r_5}^p ~ \overbrace{r_0 ~ r_1 ~ r_2 ~ r_3 ~ r_4 r_5}^p \\ r_0 ~ r_1 ~ r_2 ~ r_3 ~ \underbrace{\overbrace{r_0 ~ r_1 ~ r_2 ~ r_3 ~ r_4 ~ r_5}^p ~ r_0 ~ r_1}_{\pi[11] = 8} -\end{gather} +\end{gathered} $$ 根据扩展欧几里得算法我们可以得到一组 $x$ 和 $y$ 使得 $xk + yp = \gcd(k, p)$。通过与等式 $pk - kp = 0$ 适当叠加我们可以得到一组 $x' > 0$ 和 $y' < 0$ 使得 $x'k + y'p = \gcd(k, p)$。这意味着通过不断应用前述方程组中的方程我们可以得到新的方程组 $r_{(i + \gcd(k, p)) \bmod p} = r_{i \bmod p}$。 @@ -245,12 +245,12 @@ void compute_automaton(string s, vector>& aut) { 出于完整性考虑，我们来解决这样一个问题：给定一个数 $k \le 10^5$，以及一个长度 $\le 10^5$ 的字符串 $s$，我们需要计算 $s$ 在第 $k$ 个 Gray 字符串中的出现次数。回想起 Gray 字符串以下述方式定义： $$ -\begin{align} +\begin{aligned} g_1 &= \mathtt{a}\\ g_2 &= \mathtt{aba}\\ g_3 &= \mathtt{abacaba}\\ g_4 &= \mathtt{abacabadabacaba} -\end{align} +\end{aligned} $$ 由于其天文数字般的长度，在这种情况下即使构造字符串 $t$ 都是不可能的：第 $k$ 个 Gray 字符串有 $2^k - 1$ 个字符。然而我们可以在仅仅知道开头若干前缀函数值的情况下，有效计算该字符串末尾的前缀函数值。 @@ -260,10 +260,10 @@ $$ 我们该如何计算这些值呢？首先根据定义，初始条件为 $G[0][j] = j$ 以及 $K[0][j] = 0$。之后所有值可以通过先前的值以及使用自动机计算得到。为了对某个 $i$ 计算相应值，回想起字符串 $g_i$ 由 $g_{i - 1}$，字母表中第 $i$ 个字符，以及 $g_{i - 1}$ 三者拼接而成。因此自动机会途径下列状态： $$ -\begin{gather} +\begin{gathered} \text{mid} = \text{aut}[G[i - 1][j]][i] \\ G[i][j] = G[i - 1][\text{mid}] -\end{gather} +\end{gathered} $$ $K[i][j]$ 的值同样可被简单计算。 @@ -275,12 +275,12 @@ $$ 其中 $[\cdot]$ 当其中表达式取值为真时值为 $1$，否则为 $0$。综上，我们已经可以解决关于 Gray 字符串的问题，以及一大类与之类似的问题。举例来说，应用同样的方法可以解决下列问题：给定一个字符串 $s$ 以及一些模式 $t_i$，其中每个模式以下列方式给出：该模式由普通字符组成，当中可能以 $t_{k}^{\text{cnt}}$ 的形式递归插入先前的字符串，也即在该位置我们必须插入字符串 $t_k$ $\text{cnt}$ 次。以下是这些模式的一个例子： $$ -\begin{align} +\begin{aligned} t_1 &= \mathtt{abdeca} \\ t_2 &= \mathtt{abc} + t_1^{30} + \mathtt{abd} \\ t_3 &= t_2^{50} + t_1^{100} \\ t_4 &= t_2^{10} + t_3^{100} -\end{align} +\end{aligned} $$ 递归代入会使字符串长度爆炸式增长，他们的长度甚至可以达到 $100^{100}$ 的数量级。而我们必须找到字符串 $s$ 在每个字符串中的出现次数。 -- 2.11.0