From 10dfc008bf82c58438f13c3e752b5b8d23d09b12 Mon Sep 17 00:00:00 2001 From: sshwy Date: Thu, 18 Jul 2019 09:28:45 +0800 Subject: [PATCH] Pangu --- docs/math/index.md | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-) diff --git a/docs/math/index.md b/docs/math/index.md index 2311315c..57f82807 100644 --- a/docs/math/index.md +++ b/docs/math/index.md @@ -5,8 +5,7 @@ 举几个栗子: 1. 多项式可以优化卷积形式的背包,可以做一些字符串题 - -2. 很多 DP 类型的题都可以结合排列组合/概率期望。 +2. 很多 DP 类型的题都可以结合排列组合 / 概率期望。 * * * @@ -17,10 +16,10 @@ 3. 高精度:当数字过大,语言变量类型不足以存储时的处理方法。 4. 整除:质数、最大公约数、欧拉函数与欧拉定理、(类)欧几里德算法。 5. 同余:裴蜀定理、逆元、中国剩余定理、大步小步(BSGS)算法、阶与原根。 -6. 线性代数基础:矩阵、高斯消元(矩阵/概率期望)、线性基。 +6. 线性代数基础:矩阵、高斯消元(矩阵 / 概率期望)、线性基。 7. 复数与复平面 8. 数论反演:主要有莫比乌斯反演。 -9. 筛法:埃氏筛、欧拉筛(线性筛)、杜教筛/洲阁筛。 +9. 筛法:埃氏筛、欧拉筛(线性筛)、杜教筛 / 洲阁筛。 10. 多项式:快速傅里叶变换(FFT)、快速数论变换(NTT),拉格朗日插值、多项式的各种变换。 11. 组合数学:排列组合、卡特兰数、斯特林数、康托展开、容斥原理、抽屉原理。 12. 概率与期望 @@ -58,32 +57,32 @@ NOIP 对数学的考察还处在一个比较简单的范围。 2. 大 $\Omega$ 符号:当且仅当存在正实数 $M$ 和实数 $x_0$,使得 $\forall x\geq x_0,\ f(x)\geq Mg(x)$ ,我们就可以认为,$f(x)=\Omega (g(x))$. 大 $\text{O}$ 与大 $\Omega$ 恰好相反,即 $f(x)=\text{O}(g(x))\Leftrightarrow g(x)=\Omega(f(x))$。 3. 大 $\Theta$ 符号:大 $\Theta$ 符号是大 $\text{O}$ 和大 $\Omega$ 的结合,即 $f(x)=\text{O}(g(x))\wedge f(x)=\Omega(g(x))\ \Rightarrow f(x)=\Theta(g(x))$。 -### 整除/同余理论常见符号 +### 整除 / 同余理论常见符号 -1. 整除符号:$x\mid y$,表示$x$整除$y$,即$x$是$y$的因数。 -2. 取模符号:$x\bmod y$,表示$x$除以$y$得到的余数。 +1. 整除符号:$x\mid y$,表示 $x$ 整除 $y$,即 $x$ 是 $y$ 的因数。 +2. 取模符号:$x\bmod y$,表示 $x$ 除以 $y$ 得到的余数。 3. 互质符号:$x\perp y$,表示 x,y 互质。 4. 最小公倍数:$\gcd(x,y)$,在无混淆意义的时侯可以写作 $(x,y)$。 5. 最大公约数:$\operatorname{lcm}(x,y)$,在无混淆意义的时侯可以写作 $[x,y]$。 ### 数论函数常见符号 -求和符号:$\sum$符号,表示满足特定条件的数的和。举几个例子: +求和符号:$\sum$ 符号,表示满足特定条件的数的和。举几个例子: -- $\sum_{i=1}^ni$ 表示$1+2+\cdots+n$的和。其中$i$是一个变量,在求和符号的意义下$i$通常是**正整数或者非负整数**(除非特殊说明)。这个式子的含义可以理解为,$i$从$1$循环到$n$,所有$i$的和。这个式子用代码的形式很容易表达。当然,学过简单的组合数学的同学都知道$\sum_{i=1}^n=\frac{n(n+1)}{2}$。 -- $\sum_{S\subseteq T}|S|$表示所有被$T$包含的集合的大小的和。 -- $\sum_{p\le n,p\perp n}1$ 表示的是$n$以内有多少个与$n$互质的数,即$\varphi(n)$,$\varphi$是欧拉函数。 +- $\sum_{i=1}^ni$ 表示 $1+2+\cdots+n$ 的和。其中 $i$ 是一个变量,在求和符号的意义下 $i$ 通常是**正整数或者非负整数**(除非特殊说明)。这个式子的含义可以理解为,$i$ 从 $1$ 循环到 $n$,所有 $i$ 的和。这个式子用代码的形式很容易表达。当然,学过简单的组合数学的同学都知道 $\sum_{i=1}^n=\frac{n(n+1)}{2}$。 +- $\sum_{S\subseteq T}|S|$ 表示所有被 $T$ 包含的集合的大小的和。 +- $\sum_{p\le n,p\perp n}1$ 表示的是 $n$ 以内有多少个与 $n$ 互质的数,即 $\varphi(n)$,$\varphi$ 是欧拉函数。 求积符号:$\prod$ 符号,表示满足特定条件的数的积。举几个例子: -- $\prod_{i=1}^ni$表示$n$的阶乘,即$n!$。在组合数学常见符号中会讲到。 -- $\prod_{i=1}^na_i$表示$a_1\times a_2\times a_3\times \cdots\times a_n$的积。 -- $\prod_{x|d}x$表示$d$的所有因数的乘积。 +- $\prod_{i=1}^ni$ 表示 $n$ 的阶乘,即 $n!$。在组合数学常见符号中会讲到。 +- $\prod_{i=1}^na_i$ 表示 $a_1\times a_2\times a_3\times \cdots\times a_n$ 的积。 +- $\prod_{x|d}x$ 表示 $d$ 的所有因数的乘积。 在行间公式中,求和符号与求积符号的上下条件会放到符号的上面和下面,这一点要注意。 ### 其他常见符号 -1. 阶乘符号 $!$,$n!$ 表示 $1\times 2\times 3\times \cdots\times n$。 +阶乘符号 $!$,$n!$ 表示 $1\times 2\times 3\times \cdots\times n$。 -另外,还请大家学好高一数学,这样学习数论的时侯会省很多功夫。 \ No newline at end of file +另外,还请大家学好高一数学,这样学习数论的时侯会省很多功夫。 -- 2.11.0