【学习笔记】数论、数学—常见定理、结论、性质汇总

辰星凌 · 2019-12-05 17:32:39 · 个人记录

【学习笔记】数论、数学—常见定理、结论、性质汇总

\color{red}{\mathcal{M}}\color{#fbe044}{\mathcal{y}}\ \ \color{green}{\mathcal{B}}\color{#46f1e7}{\mathcal{l}}\color{blue}{\mathcal{o}}\color{purple}{\mathcal{g}}

〇：【不知道放哪儿好的内容】

1.【和式】

【推导结论】

• \sum_{i=1}^{n}i=\frac{n(n+1)}{2}
• \sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}
• \sum_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}

2.【下降幂、上升幂】

【基本性质、定理】

• x^{\underline{n}}=(x-1)^{\underline{n-1}}x=\frac{(x)!}{(x-n)!}=\prod_{i=x-n+1}^{x} i$ $(x^{\underline{0}}=1)
• x^{\overline{n}}=(x+1)^{\overline{n-1}}x=\frac{(x+n-1)!}{(x-1)!}=\prod_{i=x}^{x+n-1} i$ $(x^{\overline{0}}=1)

【推导结论】

• x^{\underline{n}}=(-1)^n(-x)^{\overline{n}}
• x^{\overline{n}}=(-1)^n(-x)^{\underline{n}}
• x^{\underline{n}}=A_{x}^{n}
• x^{\overline{n}}=A_{x+n-1}^{n}

3.【三角函数】

【基本性质、定理】

(1).【函数基本关系】

• \tan \alpha=\frac{\sin \alpha}{\cos \alpha}
• \cot \alpha=\frac{\cos \alpha}{\sin \alpha}
• \sin \alpha\csc \alpha=1
• \cos \alpha\sec \alpha=1
• \tan \alpha\cot \alpha=1
• \sin^{2}\alpha+\cos^{2}\alpha=1
• \sec^{2}\alpha-\tan^{2}\alpha=1
• \csc^{2}\alpha-\cot^{2}\alpha=1

(2).【秀导公式】

• \sin(-\alpha)=-\sin \alpha
• \cos(-\alpha)=\cos \alpha
• \tan(-\alpha)=-\tan \alpha
• \cot(-\alpha)=-\cot \alpha
• \sin(\pi+\alpha)=-\sin \alpha
• \cos(\pi+\alpha)=-\cos \alpha
• \tan(\pi+\alpha)=\tan \alpha
• \cot(\pi+\alpha)=\cot \alpha
• \sin(\pi-\alpha)=\sin \alpha
• \cos(\pi-\alpha)=-\cos \alpha
• \tan(\pi-\alpha)=-\tan \alpha
• \cot(\pi-\alpha)=-\cot \alpha
• \sin(\frac{1}{2}\pi-\alpha)=\cos \alpha
• \cos(\frac{1}{2}\pi-\alpha)=\sin \alpha
• \tan(\frac{1}{2}\pi-\alpha)=\cot \alpha
• \cot(\frac{1}{2}\pi-\alpha)=\tan \alpha

(3).【和角公式】

• \sin(\alpha+\beta)=\sin \alpha\cos \beta+\cos \alpha\sin \beta
• \sin(\alpha-\beta)=\sin \alpha\cos \beta-\cos \alpha\sin \beta
• \cos(\alpha+\beta)=\cos \alpha\cos \beta-\sin \alpha\sin \beta
• \cos(\alpha-\beta)=\cos \alpha\cos \beta+\sin \alpha\sin \beta
• \tan(\alpha+\beta)=\frac{\tan \alpha+\tan \beta}{1-\tan \alpha\tan \beta}
• \tan(\alpha-\beta)=\frac{\tan \alpha-\tan \beta}{1+\tan \alpha\tan \beta}

(4).【积化和差】

（同 \cos 异 \sin，\sin \sin 负负）

• \cos \alpha\cos \beta=\frac{1}{2}[\cos(\alpha+\beta)+\cos(\alpha-\beta)]
• \sin \alpha\sin \beta=-\frac{1}{2}[\cos(\alpha+\beta)-\cos(\alpha-\beta)]
• \sin \alpha\cos \beta=\frac{1}{2}[\sin(\alpha+\beta)+\sin(\alpha-\beta)]
• \cos \alpha\sin \beta=\frac{1}{2}[\sin(\alpha+\beta)-\sin(\alpha-\beta)]

(5).【和差化积】

• \sin \alpha+\sin \beta=2\sin(\frac{\alpha+\beta}{2})\cos(\frac{\alpha-\beta}{2})
• \cos \alpha+\cos \beta=2\cos(\frac{\alpha+\beta}{2})\cos(\frac{\alpha-\beta}{2})
• \sin \alpha-\sin \beta=2\cos(\frac{\alpha+\beta}{2})\sin(\frac{\alpha-\beta}{2})
• \cos \alpha-\cos \beta=-2\sin(\frac{\alpha+\beta}{2})\sin(\frac{\alpha-\beta}{2})
• \tan \alpha+\tan \beta=\frac{\sin(\alpha+\beta)}{\cos \alpha\cos \beta}

(6).【倍角公式】

• \sin 2\alpha=2\sin \alpha\cos \alpha
• \cos 2\alpha=\cos^2 \alpha-\sin^2 \alpha=2\cos^2 \alpha-1=1-2\sin^2 \alpha
• \tan 2\alpha=\frac{2\tan \alpha}{1-\tan^2 \alpha}

(7).【半角公式】

• \sin \frac{\alpha}{2}=\pm\sqrt{\frac{1-\cos \alpha}{2}}
• \cos \frac{\alpha}{2}=\pm \sqrt{\frac{1+\cos \alpha}{2}}
• \tan \frac{\alpha}{2}=\pm \sqrt{\frac{1-\cos \alpha}{1+\cos \alpha}}
• \tan \frac{\alpha}{2}=\frac{1-\cos \alpha}{\sin \alpha}=\frac{\sin \alpha}{1+\cos \alpha}

(8).【万能公式】

• \sin \alpha=\frac{2\tan \frac{\alpha}{2}}{1+\tan^{2} \frac{\alpha}{2}}
• \cos \alpha=\frac{1-\tan^{2} \frac{\alpha}{2}}{1+\tan^{2} \frac{\alpha}{2}}
• \tan \alpha=\frac{2\tan \frac{\alpha}{2}}{1-\tan^{2} \frac{\alpha}{2}}

(9).【正弦定理、余弦定理】

• \cos A=\frac{b^{2}+c^{2}-a^{2}}{2bc}
• \cos B=\frac{a^{2}+c^{2}-b^{2}}{2ac}
• \cos C=\frac{a^{2}+b^{2}-c^{2}}{2ab}

(10).【常见反三角函数】

• \arcsin \alpha+\arccos \alpha=\frac{\pi}{2}

(11).【辅助角公式】

• a\sin \alpha+b\cos \alpha=\sqrt{a^2+b^2}\sin(\alpha+\arctan\frac{b}{a})\ (a>0)

4.【单位根】

【基本性质、定理】

• \omega_{n}^{k}=\cos(\frac{2\pi k}{n})+\sin(\frac{2\pi k}{n})i
• \omega_{n}^{k}=g^{\frac{k(P-1)}{n}}\mod P$ $(P=k2^{t}+1,P\in \{Prime\})

【推导结论】

• \omega_{n}^{k}=(\omega_{n}^{1})^{k}
• \omega_{n}^{j}\omega_{n}^{k}=\omega_{n}^{j+k}
• \omega_{2n}^{2k}=\omega_{n}^{k}
• \omega_{n}^{(k+n/2)}=-\omega_{n}^{k}$ $(n$ 为偶数 $)
• \sum_{i=1}^{n-1}\omega_{n}^{i}=0

一：【基本数论、数学知识】

1.【斐波那契数列（Fibonacci）】

【基本性质、定理】

【推导结论】

• \sum_{i=1}^{n}{f_{i}}=f_{n+2}-1
• \sum_{i=1}^{n}{f_{2i-1}}=f_{2n}
• \sum_{i=1}^{n}{f_{2i}}=f_{2n+1}-1
• \sum_{i=1}^{n}{(f_{i})^2}=f_{i}f_{i+1}
• f_{n+m}=f_{n-1}f_{m-1}+f_{n}f_{m}
• (f_{n})^2=(-1)^{(n-1)}+f_{n-1}f_{n+1}
• f_{2n-1}=(f_{n})^2-(f_{n-2})^2
• f_{n}=\frac{f_{n+2}+f_{n-2}}{3}
• \frac{f_{i}}{f_{i-1}} \approx \frac{\sqrt{5}-1}{2} \approx 0.618

2.【最大公约数（GCD）和最小公倍数（LCM）】

【基本性质、定理】

• \gcd(a,b)=\gcd(b,a-b)$ $(a>b)
• \gcd(a,b)=\gcd(b,a \mod b)
• \gcd(a,b)\operatorname{lcm}(a,b)=ab

【推导结论】

• k | \gcd(a,b) \iff k|a$ 且 $k|b
• \gcd(k,ab)=1 \iff \gcd(k,a)=1$ 且 $\gcd(k,b)=1

• 在 Fibonacc 数列中求相邻两项的 \gcd 时，辗转相减次数等于辗转相除次数。

3.【裴蜀（Bézout）定理】

【基本性质、定理】

• 设 a,b 是不全为零的整数，则存在整数 x,y , 使得 ax+by=\gcd(a,b)

• \gcd(a,b)|d \iff \exists x,y\in\mathbb{Z},ax+by=d

【推导结论】

• 设不定方程 ax+by=\gcd(a,b) 的一组特解为 \begin{cases}x=x_0\\ y=y_0\end{cases}，则 ax+by=c (\gcd(a,b)|c) 的通解为 \begin{cases}x=\frac{c}{\gcd(a,b)}x_0+k\frac{b}{\gcd(a,b)}\\ y=\frac{c}{\gcd(a,b)}y_0-k\frac{a}{\gcd(a,b)}\end{cases}(k\in\mathbb{Z}) 。【模板】

4.【欧拉函数】

【基本性质、定理】

【推导结论】

• p>2 \Longrightarrow [\varphi(p)\mod 2=0]
• p\in\{Prime\} \Longrightarrow \varphi(p^{k})=p^{k}-p^{k-1}
• f(n)=\sum_{i=1}^{n}[\gcd(i,k)=1]=\frac{n}{k}\varphi(k)+f(n\mod k)

5.【同余运算】

【基本性质、定理】

• \begin{cases}a\equiv b(\bmod m)\\ c\equiv d(\bmod m)\end{cases}\Longrightarrow a+c\equiv b+d(\bmod m)
• \begin{cases}a\equiv b(\bmod m)\\ c\equiv d(\bmod m)\end{cases}\Longrightarrow a-c\equiv b-d(\bmod m)
• a\equiv b(\bmod m)\Longrightarrow ak\equiv bk(\bmod m)
• ka\equiv kb(\bmod m),\gcd(k,m)=1\Longrightarrow a\equiv b(\bmod m)

6.【费马小定理及其扩展】

【基本性质、定理】

• P\in\{Prime\},P\nmid a\Longrightarrow a^{P-1}=1(\bmod P)

【推导结论】

• 对于任意多项式 F(x)=\sum_{i=0}^{\infty}a_i x^i（a_i 对一个质数 P 取模），若满足 a_{0}\equiv 1(\bmod P)，则 \forall n\leqslant P,F^{P}(x)\equiv 1(\bmod x^{n}) 。【例题】

7.【欧拉定理及其扩展】

【基本性质、定理】

• \gcd(a,m)=1\Longrightarrow a^{\varphi(m)}\equiv 1(\bmod m)
• \gcd(a,m)=1\Longrightarrow a^{b} \equiv a^{b\mod \varphi(m)}(\bmod m)

【推导结论】

8.【孙子定理/中国剩余定理（CRT）及其扩展】

【基本性质、定理】

• 若 m_1,m_2...m_k 两两互素，则同余方程组 \begin{cases}x\equiv a_{1}\left(\bmod m_{1}\right)\\ x\equiv a_{2}\left(\bmod m_{2}\right)\\ \vdots\\ x\equiv a_{k}\left(\bmod m_{k}\right)\end{cases} 有唯一解为：x=\sum_{i=1}^{k}a_iM_iM_i^{-1}, 其中 M_i=\prod_{j\neq i}m_j 。【模板】

9.【佩尔（Pell）方程】

【基本性质、定理】

• 形如 x^2-Dy^2=1 (D\in\mathbb{N^{*}}\text{且为非平方数}) 的方程被称为第一类佩尔方程。设它的一组最小正整数解为 \begin{cases}x=x_0\\ y=y_0\end{cases}, 则其第 n 个解满足：x_n+\sqrt{D}y_n=(x_0+\sqrt{D}y_0)^{n+1}, 递推式为 \begin{cases}x_n=x_0x_{n-1}+Dy_0y_{n-1}\\ y_n=x_0y_{n-1}+y_0x_{n-1}\end{cases} 。【例题】

• 形如 x^2-Dy^2=-1 (D\in\mathbb{N^{*}}\text{且为非平方数}) 的方程被称为第二类佩尔方程。设它的一组最小正整数解为 \begin{cases}x=x_0\\ y=y_0\end{cases}, 则其第 n 个解满足：x_n+\sqrt{D}y_n=(x_0+\sqrt{D}y_0)^{2n+1} 。递推式略。

10.【勾股方程/勾股数组】

【基本性质、定理】

• 方程 x^2+y^2=z^2 的正整数通解为 \begin{cases}x=k(u^2-v^2)\\ y=2kuv\\ z=k(u^2+v^2)\end{cases}(u,v\in\{Prime\},k\in\mathbb{N^{*}}), 且均满足 \gcd(x,y,z)=k 。

二：【组合数学】

1.【排列与组合数】

【基本性质、定理】

• C_{n}^{k}C_{k}^{m}=C_{n}^{m}C_{n-m}^{k-m}

【推导结论】

• ij=C_{i+j}^{2}-C_{i}^{2}-C_{j}^{2}
• \sum_{i=0}^{n}C_{n-i}^{i}=fib_{n+1}

2.【卢卡斯定理】

【基本性质、定理】

3.【库默尔定理】

【基本性质、定理】

4.【牛顿二项式定理】

【基本性质、定理】

• (x+y)^{n}=\sum_{i=0}^{n}C_{n}^{i}x^{n-i}y^i

【推导结论】

• \sum_{i=0}^{n}C_n^{i}=2^n
• \sum_{i=0}^{n}iC_n^{i}=n2^{n-1}
• \sum_{i=0}^{n}i^2C_n^{i}=n(n+1)2^{n-1}

5.【广义牛顿二项式定理】

【基本性质、定理】

• C_{r}^{n}=\begin{cases}0&n<0,r\in\mathbb{R}\\ 1&n=0,r\in\mathbb{R}\\ \frac{r(r-1)\cdots(r-n+1)}{n!}&n>0,r\in\mathbb{R}\end{cases}
• (1+x)^{-n}=\sum_{i=0}^{\infty}C_{-n}^{i}x^{i}=\sum_{i=0}^{\infty}(-1)^iC_{n+i-1}^{i}x^i

6.【卡特兰数 (Catalan)】

【基本性质、定理】

【推导结论】

7.【斯特林数 (Stirling)】

【基本性质、定理】

【推导结论】

• n!=\sum_{i=0}^{n}s_{n}^{i}
• x^{\overline{n}}=\sum_{i=0}^{n}s_{n}^{i}x^i
• x^{\underline{n}}=\sum_{i=0}^{n}s_{n}^{i}x^i(-1)^{n-i}
• x^n=\sum_{i=0}^{x,n}S_{n}^{i}x^{\underline{i}}
• x^{n}=\sum_{i=0}^{x,n}S_{n}^{i}x^{\overline{i}}(-1)^{n-i}
• \sum_{i=1}^{n}S_{n}^{i}s_{i}^{m}=\sum_{i=0}^{n}s_{n}^{i}S_{i}^{m}
• \sum_{i=0}^{n} i^{k}=\sum_{j=0}^{n}j!S_{k}^{j}C_{n+1}^{j+1}

8.【贝尔数 (Bell)】

【基本性质、定理】

9.【Polya 定理】

【基本性质、定理】

10.【经典容斥原理】

【推导结论】

11.【生成函数】

【推导结论】

(1).【常用普通生成函数 (OGF) 收敛性式】

• \sum_{i=0}^{\infty}x^i=\frac{1}{1-x}
• \sum_{i=0}^{\infty}a^ix^i=\frac{1}{1-ax}
• \sum_{i=0}^{\infty}(i+1)x^i=\frac{1}{(1-x)^2}
• \sum_{i=0}^{\infty}C_{n}^{i}x^i=(1+x)^n
• \sum_{i=0}^{\infty}C_{n+i-1}^{i}x^i=\frac{1}{(1-x)^n}

(2).【常用指数生成函数 (EGF) 收敛性式】

• \sum_{i=0}^{\infty}\frac{x^i}{i!}=e^x
• \sum_{i=0}^{\infty}\frac{x^{2i}}{(2i)!}=\frac{e^x+e^{-x}}{2}
• \sum_{i=0}^{\infty}\frac{x^{2i+1}}{(2i+1)!}=\frac{e^x-e^{-x}}{2}

三：【各种反演】

1.【欧拉反演】

【基本性质、定理】

【推导结论】

• \gcd(i,j)=\sum_{d|i,d|j} \varphi(d)

2.【狄利克雷卷积 (Dirichlet) 与莫比乌斯反演 (Mobius) 】

【基本性质、定理】

• (f \ast g)(n)=\sum_{d | n} f(d) g(\frac{n}{d})=
• f(n)=\sum_{n | d} g(d) \Longrightarrow$ $g(n)=\sum_{n | d} \mu(\frac{d}{n}) f(d)
• f(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} g(dk) \Longrightarrow$ $g(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d) f(dk)

【推导结论】

(1).【GCD 和 LCM】

• [\gcd(i,j)=1]=\sum_{d|i,d|j} \mu(d)

(2).【除数函数】

(3).【莫比乌斯函数】

3.【二项式反演】

【基本性质、定理】

• f(n)=\sum_{i=0}^{n}C_{n}^{i}g(i) \Longleftrightarrow$ $g(n)=\sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}f(i)
• f(n)=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}g(i)\Longleftrightarrow$ $g(n)=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}f(i)
• f(n)=\sum_{i=n}^{?}(-1)^{i}C_{i}^{n}g(i)\Longleftrightarrow$ $g(n)=\sum_{i=n}^{?}(-1)^{i}C_{i}^{n}f(i)
• f(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}C_{n}^{i}C_{m}^{j}g(i,j) \Longleftrightarrow$ $g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}(-1)^{n+m-i-j}C_{n}^{i}C_{m}^{j}f(i,j)
• f(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}(-1)^{i+j}C_{n}^{i}C_{m}^{j}g(i,j) \Longleftrightarrow$ $g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}(-1)^{i+j}C_{n}^{i}C_{m}^{j}f(i,j)
• f(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}(-1)^{i+j}C_{i}^{n}C_{j}^{m}g(i,j) \Longleftrightarrow$ $g(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}(-1)^{i+j}C_{i}^{n}C_{j}^{m}f(i,j)

4.【斯特林反演】

【基本性质、定理】

• f(n)=\sum_{i=0}^{n} S_{n}^{i} g(i) \Longleftrightarrow$ $g(n)=\sum_{i=0}^{n}(-1)^{n-i} s_{n}^{i} g(i)
• f(n)=\sum_{i=0}^{n}s_{n}^{i}g(i)\Longleftrightarrow$ $g(n)=\sum_{i=0}^{n}(-1)^{n-i}S_{n}^{i}f(i)
• f(n)=\sum_{i=n}^{?} S_{i}^{n} g(i) \Longleftrightarrow$ $g(n)=\sum_{i=n}^{?}(-1)^{i-n} s_{i}^{n} g(i)
• f(n)=\sum_{i=n}^{?}s_{i}^{n}g(i)\Longleftrightarrow$ $g(n)=\sum_{i=n}^{?}(-1)^{i-n}S_{i}^{n}f(i)

5.【单位根反演】

【基本性质、定理】

• [n|k]=\frac{\sum_{i=0}^{n-1}w_{n}^{ik}}{n}
• [a=b]=\frac{\sum_{i=0}^{n-1} w_{n}^{a i} w_{n}^{-i b}}{n}(a,b<n)

【推导结论】

6.【子集反演】

【基本性质、定理】

7.【最值反演（Min-Max 容斥）】

【基本性质、定理】

• \max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T)
• \min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\max(T)
• E(\min(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\max(T))

【推导结论】

• \text{K-th}\max(S)=\sum_{T\subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}\min(T)

8.【拉格朗日反演】

【基本性质、定理】

四：【数论筛法】

1.【杜教筛】

【基本性质、定理】

【推导结论】

五：【导数与积分】

1.【导数】

【基本性质、定理】

• f'(x)=\lim\limits_{\Delta x \rightarrow 0} \frac{\Delta y}{\Delta x}=\lim\limits_{\Delta x \rightarrow 0} \frac{f(x+\Delta x)-f(x)}{\Delta x}
• [f(x)\pm g(x)]'=f'(x)\pm g'(x)
• [f(x)g(x)]'=f'(x)g(x)+f(x)g'(x)
• [\frac{f(x)}{g(x)}]'=\frac{f'(x)g(x)-f(x)g'(x)}{[g(x)]^2}
• \frac{d}{dx}f(g(x))=\frac{df}{dg}(g(x))\frac{dg}{dx}(x)

【基本初等函数的导数公式】

• 若 f(x)=C (C 为常数 )，则 f'(x)=0

• 若 f(x)=x^{a} (\alpha \in \mathbb{Q}^{*})，则 f'(x)=ax^{a-1}

• 若 f(x)=sin(x)，则 f'(x)=cos(x)

• 若 f(x)=cos(x)，则 f'(x)=-sin(x)

• 若 f(x)=a^x，则 f'(x)=a^x\ln a

• 若 f(x)=e^x，则 f'(x)=e^x

• 若 f(x)=\log_{a}x，则 f'(x)=\frac{1}{x\ln a}

• 若 f(x)=\ln x，则 f'(x)=\frac{1}{x}

2.【积分】

【基本性质、定理】

• \int_{a}^{b} f(x)\mathrm{d}x=\sum\limits_{i=1}^{n} f(\xi_{i})\Delta x_i=\lim\limits_{n \rightarrow \infty} \sum\limits_{i=1}^{n} f[a+\frac{i}{n}(b-a)] \frac{b-a}{n}
• \int_{a}^{b}kf(x)\mathrm{d}x=k\int_{a}^{b} f(x)\mathrm{d}x
• \int_{a}^{b}[f(x)\pm g(x)]\mathrm{d}x=\int_{a}^{b}f(x)\mathrm{d}x\pm \int_{a}^{b}g(x)\mathrm{d}x
• \int_{a}^{b}f(x)\mathrm{d}x=\int_{a}^{c}f(x)\mathrm{d}x+\int_{c}^{b}f(x)\mathrm{d}x
• \int_{a}^{b}f(x)\mathrm{d}x=-\int_{b}^{a}f(x)\mathrm{d}x
• \int_{a}^{a}f(x)\mathrm{d}x=0

【基本积分公式】

• \int k\,\mathrm{d} x=kx+C$ $(C$ 为常数 $)
• \int x^a\,\mathrm{d}x=\frac{x^{a+1}}{a+1}+C$ $(a\neq -1)
• \int \frac{\mathrm{d}x}{x}=\ln|x|+C
• \int e^x\,\mathrm{d}x=e^x+C
• \int a^x\,\mathrm{d}x=\frac{a^x}{\ln a}+C
• \int \frac{\mathrm{d}x}{1+x^2}=arctan(x)+C
• \int \frac{\mathrm{d}x}{\sqrt{1-x^2}}=arcsin(x)+C
• \int cos(x)\,\mathrm{d}x=sin(x)+C
• \int sin(x)\,\mathrm{d}x=-cos(x)+C
• \int \frac{\mathrm{d}x}{cos^2(x)}\,\mathrm{d}x=\int sec^2(x)\,\mathrm{d}x=tan(x)+C
• \int \frac{\mathrm{d}x}{sin^2(x)}\,\mathrm{d}x=\int csc^2(x)\,\mathrm{d}x=-cot(x)+C
• \int sec(x)tan(x)\,\mathrm{d}x=sec(x)+C
• \int csc(x)cot(x)\,\mathrm{d}x=-csc(x)+C

• 高等数学积分表 \text{147} 个积分公式推导【高等数学吧】

六：【多项式全家桶】

1.【多项式乘法】

【基本性质、定理】

• F\left(\omega_{n}^{k}\right)=F l\left(\omega_{n / 2}^{k}\right)+\omega_{n}^{k} F R\left(\omega_{n / 2}^{k}\right) \\ F\left(\omega_{n}^{k+n / 2}\right)=F L\left(\omega_{n / 2}^{k}\right)-\omega_{n}^{k} F R\left(\omega_{n / 2}^{k}\right) \end{cases}$ [【模板】](https://www.luogu.com.cn/problem/P3803)

2.【分治 FFT / NTT】

3.【位运算卷积】

【基本性质、定理】

• FWT:\left\{F_{0}=G_{0}, F_{1}=G_{0}+G_{1}\right\} \\ IFWT:\left\{G_{0}=F_{0}, G_{1}=F_{1}-F_{0}\right\} \end{cases}$ [【模板】](https://www.luogu.com.cn/problem/P4717)
• FWT:\left\{F_{0}=G_{0}+G_{1}, F_{1}=G_{1}\right\} \\ IFWT:\left\{G_{0}=F_{0}-F_{1}, G_{1}=F_{1}\right\} \end{cases}$ [【模板】](https://www.luogu.com.cn/problem/P4717)
• F W T:\left\{F_{0}=G_{0}+G_{1}, F_{1}=G_{0}-G_{1}\right\} \\ I F W T:\left\{G_{0}=\frac{F_{0}+F_{1}}{2}, G_{1}=\frac{F_{0}-F_{1}}{2}\right\} \end{cases}$ [【模板】](https://www.luogu.com.cn/problem/P4717)

4.【子集卷积】

5.【拉格朗日插值】

【基本性质、定理】

• 已知一个 n 次多项式 F(x) 不同的 n+1 处点值 (x_i,y_i)_{i\in[0,n]}，则 F(X)=\sum_{i=0}^{n}\left(y_{i}\prod_{j\neq i}\frac{X-x_{j}}{x_{i}-x_{j}}\right) 。【模板】

【推导结论】

• 已知一个 n 次多项式 F(x) 不同的 n+1 处点值 (i,y_i)_{i\in[0,n]}，则 F(m+x)=\frac{(m+x)!}{(m+x-n-1)!}\sum_{i=x}^{n+x}\frac{1}{m-n+i}g(n+x-i)，其中 g(i)=\frac{y_i(-1)^{n-i}}{i!(n-i)!} 。【模板】 【例题】

6.【多项式求逆】

【基本性质、定理】

• 设 F(x)=\sum_{n=0}^{\infty}a_nx^n, F^{-1}(x)=\sum_{n=0}^{\infty}b_nx^n，则 b_0=\frac{1}{a_0},b_n=\sum_{i=0}^{n-1}b_i\left(-\frac{a_{n-i}}{a_0}\right) 。【模板】

• 设 F(x)G(x)\equiv 1(\bmod x^{n}),F(x)G(x)^{\prime}\equiv 1(\bmod x^{\frac{n}{2}}), 则 G\equiv 2G^{\prime}-FG^{\prime 2}(\bmod x^{n}) 。【证明】 【模板】

7.【多项式开方】

8.【多项式除法 / 取模】

9.【多项式对数函数 / 指数函数】

10.【多项式牛顿迭代】

11.【多项式多点求值 / 快速插值】

12.【多项式三角函数】

13.【多项式反三角函数】

14.【常系数齐次线性递推】

【参考文献】

• 维基百科、百度百科及全网各大博客