28 Jan 2019 3638字 13分 次 ACM, 算法竞赛模板, and 学习笔记
如果这篇博客帮助到你，可以请我喝一杯咖啡~
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 时称为麦克劳林公式。

$$f(x)=f(a)+f^{(1)}(a)(x-a)+\frac{f^{(2)}(a)}{2!}(x-a)^2+\ldots+\frac{f^{(n)}(a)}{n!}(x-a)^n+R_n(x)$$

佩亚诺余项

$$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}+\ldots+(-1)^{n-1}\frac{x^n}{n}+R_n(x)$$

幂函数

$$[(1+x)^a]^{(n)}=a(a-1)\ldots(a-n+1)(1+x)^{a-n}\\ (1+x)^a=1+ax+\frac{a(a-1)}{2!}x^2+\dots+\frac{a(a-1)\ldots(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!}+\ldots+(-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!}+\ldots+(-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!}+\ldots+\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\ldots$$

二分求零点、三分求极值点

需要$f(x)$在区间$[l,r]$上单调/凹凸性唯一。

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); //极小值
}

自适应辛普森求积分

使用示例

这篇论文论证了加一个十五分之一的偏移收敛会比较快…

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 非质数的话，那么就要用牛顿插值法。

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;
	}
};