KMP【模板】

0

倍增求LCA【模板】

倍增求LCA

0

树状数组求逆序对【模板】

存板子

0

某一神奇的极限的多种解法

\[
\lim _ { x \rightarrow \infty } x \left[ \sin \ln \left( 1 + \frac { 3 } { x } \right) – \sin \ln \left( 1 + \frac { 1 } { x } \right) \right] = ?
\]

解法1

倒代换+拉格朗日中值定理:
\[
\begin{aligned}
\lim _ { x \rightarrow + \infty } x \left[ \sin \ln \left( 1 + \frac { 3 } { x } \right) – \sin \ln \left( 1 + \frac { 1 } { x } \right) \right] &= \lim _ { x \rightarrow \infty } \frac { \sin \ln \left( 1 + \frac { 3 } { x } \right) – \sin \ln \left( 1 + \frac { 1 } { x } \right) } { \frac { 1 } { x } }\\
& \overset{t = \frac{1}{x}}{=} \lim _ { t \rightarrow 0 ^ { + } } \frac { \sin \ln ( 1 + 3 t ) – \sin \ln ( 1 + t ) } { t }\\
由Lagrange中值定理:\\
&= \lim _ { t \rightarrow 0^ + } \frac { \ln ( 1 + 3 t ) – \ln ( t + 1 ) } { t }\\
&= \lim _ { t \rightarrow 0^ + } \frac { \ln ( 1 + 3 t )}{t} – \lim _ { t \rightarrow 0^ + } \frac { \ln ( t + 1 ) } { t }\\
&= 3 – 1\\
&= 2
\end{aligned}
\]

解法2

复合函数广义泰勒展开:

\[
\begin{aligned}
\lim _ { x \rightarrow \infty } x \left[ \sin \ln \left( 1 + \frac { 3 } { x } \right) – \sin \ln \left( 1 + \frac { 1 } { x } \right) \right] &= \lim _ { x \rightarrow \infty } x \left[ \dfrac{3}{x} + O \left ( \dfrac{3}{x}\right) – \dfrac{1}{x} – O \left ( \dfrac{1}{x}\right)\right]\\
&=\lim _ { x \rightarrow \infty } x \cdot \left( \frac { 2 } { x } + O \left( \frac { 1 } { x } \right) \right)\\
&= \lim _ { x \rightarrow \infty } 2 + \frac { \mathscr { O } \left( \frac { 1 } { x } \right) } { \frac { 1 } { x } }\\
&= 2
\end{aligned}
\]

解法3

\[
\begin{aligned}
&                        \lim _ { x \rightarrow \infty } x \left[ \sin \ln \left( 1 + \frac { 3 } { x } \right) – \sin \ln \left( 1 + \frac { 1 } { x } \right) \right] \\
&= \lim _ { x \rightarrow \infty } x \left[ 2 \cos \frac { \ln \left( 1 + \frac { 3 } { x } \right) + \ln \left( 1 + \frac { 1 } { x } \right) } { 2 } \sin \frac { \ln \left( 1 + \frac { 3 } { x } \right) – \ln \left( 1 + \frac { 1 } { x } \right) } { 2 } \right] \\
&= 2 \lim _ { x \rightarrow \infty } x \left[ \cos \frac { \ln \left( 1 + \frac { 3 } { x } \right) \left( 1 + \frac { 1 } { x } \right) } { 2 } \sin \frac { \ln \frac { \left( 1 + \frac { 3 } { x } \right) } { \left( 1 + \frac { 1 } { x } \right) } } { 2 } \right] \\
&= 2 \lim _ { x \rightarrow \infty } \left[ \frac { \sin \frac { \left( 1 + \frac { 3 } { x } \right) } { \left( 1 + \frac { 1 } { x } \right) } } { \frac { 1 } { x } } \right] \\
&= 2 \lim_{x \rightarrow +\infty} \dfrac{\cos\frac{\ln \frac{1+\frac{3}{x}}{1+\frac{1}{x}}}{2} \frac{1}{2}\times \frac{1+\frac{1}{x}}{1+\frac{3}{x}} \times \frac{-\frac{3}{x^2}\left(1+\frac{1}{x}\right ) + \frac{1}{x^2}\left(1+\frac{3}{x}\right)}{\left(1+\frac{1}{x}\right)^2}}{-\frac{1}{x^2}} \\
&= 2
\end{aligned}
\]

0

FFT-多项式乘法【模板】

UOJ的那道题

0

ST表【模板】

\(st_{i,j}\)表示以\(i\)开头\(i+2^j\)结尾的区间的最值。

初态:\(st_{i,0} = a_i\)
状态转移: \(st_{i,j} = \min/\max (st_{i,j-1}, st_{i+ 2 ^ {j-1},j-1})\)


 

0

解不定方程ax+by=c【模板】

若c不是gcd(a,b)的倍数,那么一定不存在整数解

0