测试推莫反&打LaTeX的速度

无聊,不看论文和博客我能否手推莫比乌斯反演公式?

计时开始13:34

Möbius function:
\[
\mu(n) = \left\{\begin{matrix}0 & \mathrm{if} \: n \: \mathrm{is \: NOT \: square free.}\\ (-1)^{\omega (n)} & \mathrm{if} \: n \: \mathrm{is \: square \: free.} \end{matrix}\right.
\]

To Prove:
\[
\displaystyle{F(n) = \sum_{d|n} f(d)} \Rightarrow \displaystyle{f(n) = \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right)}
\]

Proof:
\[
\begin{align} \quad \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right ) &= \sum_{d|n} \mu(d) \sum_{d|n} f \left ( \frac{n}{d} \right ) \\ &= \sum_{d|n} \mu(d) \sum_{e|\frac{n}{d}} f(e) \\ &= \sum_{d|n} \sum_{e|\frac{n}{d}} \mu(d) f(e) \end{align}
\]
From \( e | \frac{n}{d} \Rightarrow d | \frac{n}{e}\) and \( \mu \circ \mathit{1} = \iota \)we deduce that
\[
\begin{align} \quad \sum_{e|n} \mu (d) F \left ( \frac{n}{d} \right ) &= \sum_{e|n} \sum_{d|\frac{n}{e}} \mu(d) f(e) \\ &= \sum_{e|n} \left ( f(e) \cdot \sum_{d|\frac{n}{e}} \mu(d) \right ) \\ &= \sum_{e|n} f(e) \iota \left ( \frac{n}{e} \right ) \\ &= \sum_{e|n} f(e) \cdot \left\{\begin{matrix} 0 & \mathrm{if} \: e \neq n \\ 1 & \mathrm{if} \: e = n \end{matrix}\right. \\ &= f(n) \end{align}
\]

Hence \(\begin{align} \quad f(n) = \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right ) \quad \blacksquare \end{align}\)

计时结束13:47

13分钟打完以上内容

Tarjan求有向图强连通分量【模板】

KMP【模板】

倍增求LCA【模板】

倍增求LCA

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

存板子

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

\[
\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}
\]

FFT-多项式乘法【模板】

UOJ的那道题