CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
增长趋势
\[n\to+\infty,\forall p,q>0,a>1,{(\ln n)}^q\ll n^p\ll a^n\ll n!\ll n^n\]积分表
反读可得导数表，此处略。
\[\int k\,\mathrm{d}x=kx+C\\ \int x^a\,dx=\frac{x^{a+1}}{a+1}+C\\ \int\frac{1}{x}\,dx=\ln\mid x\mid +C\\ \int e^x\,dx=e^x + C\\ \int a^x\,dx=\frac{a^x}{\ln a}+C\\ \int\cos x\,dx=\sin x+C\\ \int\sin x\,dx=-\cos x+C\\ \int\frac{1}{cos^2x}\,dx=\int\sec^2 x\,dx=\tan x+C\\ \int\frac{1}{sin^2x}\,dx=\int\csc^2 x\,dx=-\cot x+C\\ \int\frac{1}{\sqrt{1-x^2}}\,dx=\arcsin x+C=-\arccos x+C\\ \int\frac{1}{1+x^2}\,dx=\arctan x+C=-arccot\,x+C\\ \int\sec x\tan x\,dx=\sec x+C\\ \int\csc x\cot x\,dx=-\csc x+C\\ \int\tan x\,dx=-\ln\mid \cos x\mid +C\\ \int\cot x\,dx=\ln\mid \sin x\mid +C\\ \int\sec x\,dx=\ln\mid \sec x+\tan x\mid +C\\ \int\csc x\,dx=\ln\mid \csc x-\cot x\mid +C\\ \int sh\,x\,dx=ch\,x+C\\ \int ch\,x\,dx=sh\,x+C\\ \int\frac{1}{x^2+a^2}\,dx=\frac{1}{a}\arctan\frac{x}{a}+C\\ \int\frac{1}{x^2-a^2}\,dx=\frac{1}{2a}\ln\mid \frac{x-a}{x+a}\mid +C\\ \int\frac{1}{\sqrt{a^2-x^2}}\,dx=\arcsin\frac{x}{a}+C\\ \int\frac{1}{\sqrt{x^2-a^2}}\,dx=\ln\mid x+\sqrt{x^2-a^2}\mid +C\\ \int\frac{1}{\sqrt{x^2+a^2}}\,dx=\ln\mid x+\sqrt{x^2+a^2}\mid +C\\\]积分求几何量
弧长
若简单闭曲线
\[\begin{cases} x=x(t),\\ y=y(t), \end{cases} t\in[\alpha,\beta]\]端点处重合（$x(\alpha)=x(\beta),y(\alpha)=y(\beta)$）且其他地方不自交，$x(t),y(t)$连续且满足
\[[x'(t)]^2+[y'(t)]^2\ne0,\forall t\in[\alpha,\beta]\]此时称曲线光滑，其长度
\[s=\int_\alpha^\beta\sqrt{[x'(t)]^2+[y'(t)]^2}\,dt\]此式可对称推广到高维空间曲线。 极坐标下，
\[r=r(\theta),\theta\in[\alpha,\beta]\]的长度为
\[s=\int_\alpha^\beta\sqrt{[r(\theta)]^2+[r'(\theta)]^2}\,d\theta\]面积
若简单闭曲线
\[\begin{cases} x=x(t),\\ y=y(t), \end{cases} t\in[\alpha,\beta]\]端点处连续（$x(\alpha)=x(\beta),y(\alpha)=y(\beta)$）且其他地方不自交，$x(t),y(t)$都逐段有连续微商，则此闭合曲线围起来的有界区域面积
\[S=-\int_\alpha^\beta x'(t)y(t)\,dt=-\int_\alpha^\beta y(t)\,dx(t)=-\oint_\Gamma y\,dx=\oint_\Gamma x\,dy\]等式右边称为曲线$\Gamma$上的积分，其计算方法是带入参数方程到定积分计算式中，积分上下限为始点与终点对应的参数值。下限并不总是小于上限，参数从下限到上限变化时对应曲线的正向（沿正向观察时，曲线所围的区域永远在左侧）。 极坐标下，连续非负曲线$r=r(\theta)$与向径$\theta=\alpha,\theta=\beta$，其中$0\leq\beta-\alpha\leq2\pi$所围成的平面图形面积
\[S=\frac{1}{2}\int_\alpha^\beta r^2(\theta)\,d\theta\]体积
记立体过 x 点且垂直于 x 轴的截面面积为$S(x)$，则其体积
\[V=\int_a^bS(x)\,dx\]连续曲线$y=f(x)\ge 0,x\in[a,b]$绕 x 轴旋转一周产生的旋转体体积
\[V=\pi\int_a^by^2\,dx\]旋转体侧面积
若曲线由参数方程
\[\begin{cases} x=x(t),\\ y=y(t), \end{cases} t\in[\alpha,\beta]\]给出，则其绕 x 轴旋转体的侧面积
\[s=2\pi\int_\alpha^\beta y(t)\sqrt{[x'(t)]^2+[y'(t)]^2}\,dt\]方向导数
设三元函数$u=f(x,y,z)$在点$P_0(x_0,y_0,z_0)$的某邻域内有定义，任意给定始于点$P_0$的射线$l$，$P(x,y,z)$为 l 上且含于定义域内的点。若极限
\[\lim_{r(p,p_0)\to0^+}\frac{f(P)-f(P_0)}{r(P,P_0)}=\lim_{r(p,p_0)\to0^+}\frac{\Delta_lf(P_0)}{r(P,P_0)}\]存在，则称该极限值为函数$f$在点$P_0$沿方向$l$的方向导数，记为 $\frac{\partial f}{\partial l}\mid _{P_0}$或$\frac{\partial f(P_0)}{\partial l}$，$\frac{\Delta_lf(P_0)}{r(P,P_0)}$称为函数在$P_0$点沿$l$方向的增量。
特别地，$\frac{\partial f(P_0)}{\partial x}$就是函数在$P_0$点沿$x$轴正向的方向导数，$y,z$轴上的方向导数同理。若函数在$P_0$点可微，则其在$P_0$沿任何方向$l$的方向导数都存在，则有以下公式
\[\frac{\partial f(P_0)}{\partial l}=(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y},\frac{\partial f}{\partial z})\mid _{P_0}\cdot\vec{l_0}\]其中$\vec{l_0}=(\cos\alpha,\cos\beta,cos\gamma)=\frac{1}{\rho}(\Delta x,\Delta y,\Delta z)$为$l$的方向余弦。
曲率
若曲线由参数方程
\[\begin{cases} x=x(t),\\ y=y(t), \end{cases} t\in[\alpha,\beta]\]给出且有二阶微商，则其在一点的曲率
\[K=\frac{\mid y''x'-y'x''\mid }{[x'^2+y'^2]^{\frac{3}{2}}}\]若$y=f(x)$，则
\[K=\frac{\mid y''\mid }{(1+y'^2)^\frac{3}{2}}\]同时记$\frac{1}{K}$为曲率半径。
空间曲线的切线与法平面
若已知曲线上一点$P(x_0,y_0,z_0)$处的切向量为$\tau(x_0,y_0,z_0)=(A,B,C)$则曲线在该点的切线方程为
\[\frac{x-x_0}A=\frac{y-y_0}B=\frac{z-z_0}C\]法平面方程为
\[A(x-x_0)+B(y-y_0)+C(z-z_0)=0\]当曲线由参数方程
\[\begin{cases} x=x(t),\\ y=y(t),\\ z=z(t), \end{cases} t\in[\alpha,\beta]\]给出时，曲线在 P 点的切向量为
\[\tau=\pm(x'(t_0),y'(t_0),z'(t_0))\]更一般地，若曲线用两曲面的交线给出
\[\begin{cases} F(x,y,z)=0,\\ G(x,y,z)=0, \end{cases}\]且在 P 点的某邻域能确定函数组$y=y(x),z=z(x)$满足$y_0=y(x_0),z_0=z(x_0)$，且$y’(x),z’(x)$存在，则曲线在 P 点的切向量
\[\tau=\pm(\frac{\partial(F,G)}{\partial(y,z)},\frac{\partial(F,G)}{\partial(z,x)},\frac{\partial(F,G)}{\partial(x,y)})\]空间曲面的切平面与法线
若已知曲面上一点$P(x_0,y_0,z_0)$处的切平面的法向量为$\vec n=(A’,B’,C’)$则曲线在该点的法线方程为
\[\frac{x-x_0}{A'}=\frac{y-y_0}{B'}=\frac{z-z_0}{C'}\]切平面方程为
\[A'(x-x_0)+B'(y-y_0)+C'(z-z_0)=0\]当曲面方程为$\pi:F(x,y,z)=0$在曲面上任取一条过 P 的曲线，设其方程为
\[\begin{cases} x=x(t),\\ y=y(t),\\ z=z(t), \end{cases} t\in[\alpha,\beta]\]此时有$F(x(t),y(t),z(t))=0$令$t=t_0$两边对 t 求导，并写成向量的内积式，得
\[(F_x,F_y,F_z)_P\cdot(x'(t_0),y'(t_0),z'(t_0))=0\]则曲线在 P 点的法向量为
\[\vec{n}=\pm(F_x,F_y,F_z)_P\]若曲线由参数方程给出
\[\begin{cases} x=x(u,v),\\ y=y(u,v),\\ z=z(u,v), \end{cases}\]则曲线在 P 点的法向量
\[\vec{n}=\pm(\frac{\partial(y,z)}{\partial(u,v)},\frac{\partial(z,x)}{\partial(u,v)},\frac{\partial(x,y)}{\partial(u,v)})\]高阶导数与泰勒公式
用$f^{(n)}(x)$表示 f(x)的 n 阶导数，只要让余项<EPS即可计算指定函数到任意精确度，特别取 a=0 时称为麦克劳林公式。
佩亚诺余项
\[R_n(x)=o((x-a)^n)\]积分余项
\[R_n(x)=\frac{1}{n!}\int_a^x(x-t)^nf^{(n+1)}(t)\,dt\]拉格朗日余项
\[R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-a)^{n+1},a<\xi<x\]柯西余项
\[R_n(x)=\frac{(x-a)^{n+1}}{n!}(1-\theta)^nf^{(n+1)}(a+\theta(x-a)),0<\theta<1\]对数函数
\[[\ln(1+x)]^{(n)}=(-1)^{n-1}(n-1)!(1+x)^{-n} \ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\dots+(-1)^{n-1}\frac{x^n}{n}+R_n(x)\]幂函数
\[[(1+x)^a]^{(n)}=a(a-1)\dots(a-n+1)(1+x)^{a-n}\\ (1+x)^a=1+ax+\frac{a(a-1)}{2!}x^2+\dots+\frac{a(a-1)\dots(a-n+1)}{n!}x^n+R_n(x)\]三角函数
\[(\sin x)^{(n)}=\sin(x+\frac{n\pi}{2})\\ \sin x=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\dots+(-1)^{k-1}\frac{x^{2k-1}}{(2k-1)!}+R*{2k}(x) \\R*{2k}(x)=(-1)^k\frac{\cos\theta x}{(2k+1)!}x^{2k+1}\\ (\cos x)^{(n)}=\cos(x+\frac{n\pi}{2})\\ \cos x=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\dots+(-1)^{k-1}\frac{x^{2k-2}}{(2k-2)!}+R*{2k-1}(x)\\ R*{2k-1}(x)=(-1)^k\frac{\cos\theta x}{(2k)!}x^{2k}\]指数函数
\[(e^x)^{(n)}=e^x\\ e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots+\frac{x^n}{n!}+R_n(x)\\ R_n(x)=\frac{e^{\theta x}}{(n+1)!}x^{n+1},\xi=\theta x,0<\theta<1\]二元函数
设$f(x,y)$在$P_0(x_0,y_0)$的某邻域$O(P_0)$内有直到$n+1$阶连续偏导数，则对$O(P_0)$内$\forall(x_0+\Delta x,y_0+\Delta y),\exists\theta\in(0,1)$，使得
\[f(x*0+\Delta x,y_0+\Delta y)=\sum*{k=0}^n\frac{1}{k!}(\frac{\partial}{\partial x}\Delta x+\frac{\partial}{\partial y}\Delta y)^kf(x_0,y_0)+R_n\]其中
\[R_n=\frac{1}{(n+1)!}(\frac{\partial}{\partial x}\Delta x+\frac{\partial}{\partial y}\Delta y)^{n+1}f(x_0+\theta\Delta x,y_0+\theta\Delta y)\]级数部分和
幂级数
快速计算幂级数的部分和$\sum_{i=1}^ni^k\mod M$可借助伯努利数，详见组合数学模板。
\[\sum_{i=1}^ni^1=\frac 1 2n(n+1)\\ \sum_{i=1}^ni^2=\frac 1 6n(n+1)(2n+1)\\ \sum_{i=1}^ni^3=\frac 1 4[n(n+1)]^2\\ \sum_{i=1}^ni^4=\frac 1{30}n(n+1)(2n+1)(3n^2+3n-1)\\ \sum_{i=1}^ni^5=\frac 1{12}[n(n+1)]^2(2n^2+2n-1)\\ \sum_{i=1}^ni^6=\frac 1{42}n(n+1)(2n+1)(3n^4+6n^3-3n+1)\]调和级数
\[n\to\infty,\sum\_{i=1}^n\frac 1 i\to\ln n+r,r\approx0.5772156649015328\dots\]二分求零点、三分求极值点
需要$f(x)$在区间$[l,r]$上单调/凹凸性唯一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
lf bs(lf l, lf r, lf f(lf x))
{
if (r - l < EPS)
return l;
lf m = (l + r) / 2;
return sgn(f(l) * f(m)) < 0 ? bs(l, m, f) : ts(m, r, f);
}
lf ts(lf l, lf r, lf f(lf x))
{
if (r - l < EPS)
return l;
lf d = (r - l) / 3, lm = l + d, rm = r - d;
return f(lm) < f(rm) ? ts(l, rm, f) : ts(lm, r, f); //极小值
}
自适应辛普森求积分
这篇论文论证了加一个十五分之一的偏移收敛会比较快…
1
2
3
4
5
6
7
8
9
10
11
12
struct Simpson
{
lf simpson(lf a, lf b, lf f(lf x))
{
return (f(a) + 4 * f((a + b) / 2) + f(b)) * (b - a) / 6;
}
lf ask(lf a, lf b, lf f(lf x), lf e = EPS)
{
lf c = (a + b) / 2, L = simpson(a, c, f), R = simpson(c, b, f), delta = (L + R - simpson(a, b, f)) / 15;
return fabs(delta) < e ? L + R + delta : ask(a, c, f, e / 2) + ask(c, b, f, e / 2);
}
};
插值法
拉格朗日插值法：插值多项式和插值基函数的形式对称，容易编程。但是，增加节点时，需要重新计算每一个插值基函数。要在$\pmod p$意义下进行的话，那么 p 只能是质数。 牛顿插值法：当插值节点增加时，之前已计算的结果仍然能用，每增加一个节点，只要再增加一项即可，从而避免了重复性计算。如果要 mod 非质数的话，那么就要用牛顿插值法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
typedef complex<lf> Coord;
#define X real()
#define Y imag()
struct Lagrange
{
lf ask(const vector<Coord> &p, lf x) //返回p确定的多项式函数在x处的值
{
lf ret = 0;
for (int i = 0; i < p.size(); ++i)
{
lf tmp = p[i].Y;
for (int j = 0; j < p.size(); ++j)
if (i != j)
tmp *= (x - p[j].X) / (p[i].X - p[j].X);
ret += tmp;
}
return ret;
}
vector<lf> ask(vector<Coord> p) //返回p确定的多项式系数向量
{
vector<lf> ret(p.size()), sum(p.size());
ret[0] = p[0].Y, sum[0] = 1;
for (int i = 1; i < p.size(); ++i)
{
for (int j = p.size() - 1; j >= i; --j)
p[j].Y = (p[j].Y - p[j - 1].Y) / (p[j].X - p[j - i].X);
for (int j = i; ~j; --j)
sum[j] = (j ? sum[j - 1] : 0) - sum[j] * p[i - 1].X,
ret[j] += sum[j] * p[i].Y;
}
return ret;
}
};
struct Newton
{
lf differenceQuotient(const vector<Coord> &p, int k) //计算差商
{
lf ret = 0;
for (int i = 0; i <= k; ++i)
{
lf tmp = p[i].Y;
for (int j = 0; j <= k; ++j)
if (i != j)
tmp /= p[i].X - p[j].X;
ret += tmp;
}
return ret;
}
lf ask(const vector<Coord> &p, lf x)
{
lf ret = p[0].Y;
for (int i = 1; i < p.size(); ++i)
{
lf tmp = differenceQuotient(p, i); //多次求，可O(n^3)预处理优化
for (int j = 0; j < i; ++j)
tmp *= x - p[j].X;
ret += tmp;
}
return ret;
}
};