「bzoj4231」回忆树 - KMP+AC自动机/后缀自动机

发表于 2018-01-30 更新于 2019-06-10 分类于 OI Valine：

题目大意

回忆树是树。
具体来说，是$n$个点$n-1$条边的无向连通图，点标号为$1\sim n$，每条边上有一个字符（出于简化目的，我们认为只有小写字母）。
对一棵回忆树来说，回忆当然是少不了的。
一次回忆是这样的：你想起过往，触及心底…唔,不对，我们要说题目。
这题中我们认为回忆是这样的：给定$2$个点$u,v$($u$可能等于$v$)和一个非空字符串$s$，问从$u$到$v$的简单路径上的所有边按照到$u$的距离从小到大的顺序排列后，边上的字符依次拼接形成的字符串中给定的串$s$出现了多少次。

阅读全文 »

泰勒公式推导笔记

发表于 2018-01-29 更新于 2019-06-20 分类于 OI Valine：

多项式的泰勒公式

若$p(x)$是$n$次多项式。

$p(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n \tag{1}$

把该多项式微分$n$次。

$p'(x)=1\cdot a_1+2\cdot a_2x+3\cdot a_3x^2+\cdots+n\cdot a_nx^{n-1}$ $p''(x)=1\cdot2\cdot a_2+2\cdot3\cdot a_3x+\cdots+(n-1)n\cdot a_nx^{n-2}$ $p'''(x)=1\cdot2\cdot3\cdot a_3+\cdots(n-2)(n-1)na_nx^{n-3}$ $\cdots\cdots$ $p^{(n)}(x)=1\cdot2\cdot3\cdots n\cdot a_n$

在这些式子中令$x=0$，即可得到：

$a_0=p(0),a_1=\frac{p'(0)}{1!},a_2=\frac{p''(0)}{2!},a_3=\frac{p'''(0)}{3!},\cdots,a_n=\frac{p^{(n)}(0)}{n!}$

将这些系数代回$(1)$式得到：

$p(x)=p(0)+\frac{p'(0)}{1!}x+\frac{p''(0)}{2!}x^2+\frac{p'''(0)}{3!}x^3+\cdots+\frac{p^{(n)}(0)}{n!}x^n\tag{2}$

当然我们也可以以$(x-x_0)$的幂去展开多项式，此处的$x_0$时$x$的一个特殊取值（常数）。

$p(x)=A_0+A_1(x-x_0)+A_2(x-x_0)^2+A_3(x-x_0)^3+\cdots+A_n(x-x_0)^n \tag{3}$

令$x-x_0=\xi$，则$p(x)=p(x_0+\xi)=P(\xi)$，对于多项式：

$P(\xi)=A_0+A_1\xi+A_2\xi^2+A_3\xi^3+\cdots+A_n\xi^n$

根据上述所推导的系数，可知：

$A_0=P(0),A_1=\frac{P'(0)}{1!},A_2=\frac{P''(0)}{2!},A_3=\frac{P'''(0)}{3!},\cdots,A_n=\frac{P^{(n)}(0)}{n!}$

又有：

$P(\xi)=p(x_0+\xi),P'(\xi)=p'(x_0+\xi),P''(\xi)=p''(x_0+\xi),P'''(\xi)=p'''(x_0+\xi),\cdots$

因此：

$P(0)=p(x_0),P'(0)=p'(x_0),P''(0)=p''(x_0),P'''(0)=p'''(x_0),\cdots$

得到系数表示：

$A_0=p(x_0),A_1=\frac{p'(x_0)}{1!},A_2=\frac{p''(x_0)}{2!},A_3=\frac{p'''(x_0)}{3!},\cdots,a_n=\frac{p^{(n)}(x_0)}{n!}$

代入$(3)$式可得：

$p(x)=p(x_0)+\frac{p'(x_0)}{1!}(x-x_0)+\frac{p''(x_0)}{2!}(x-x_0)^2+\cdots+\frac{p^{(n)}(x_0)}{n!}(x-x_0)^n \tag{4}$

将公式$(4)$与$x_0=0$时的特殊情况$(2)$均称为泰勒公式，$(2)$也被称作麦克劳林公式。

附注$(5)$

根据上述推导，显然有这样的推论：
若多项式$p(x)$的形式为：
$p(x)=c_0+\frac{c_1}{1!}(x-x_0)+\frac{c_2}{2!}(x-x_0)^2+\frac{c_3}{3!}(x-x_0)^3+\cdots+\frac{c_n}{n!}(x-x_0)^n$
则必有：
$p(x_0)=c_0,p'(x_0)=c_1,p''(x_0)=c_2,\ldots,p^{(n)}(x_0)=c_n$

任意函数的展开式

考虑一个一般并不是多项式的任意函数$f(x)$，它定义在一个区间$\mathscr{X}$内。
假设$f(x)$在$\mathscr{X}$中的某一点$x_0$有直到$n$项为止的各阶导数存在，也就是说，在$x_0$某一邻域内存在有直到$n-1$阶为止的各阶导数：

$f'(x),f''(x),f'''(x),\ldots,f^{(n-1)}(x)$

此外，它在点$x_0$还有$n$阶导数$f^{(n)}(x)$，于是，按照$(4)$的形式，对于函数$f(x)$也可以作出一个多项式：

$p_n(x)=f(x_0)+\frac{f'(x_0)}{1!}(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\cdots+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n \tag{6}$

根据附注$(5)$，可知这个多项式与其直到$n$阶前的导数与在点$x_0$与函数$f(x)$及其导数有着相同的值。

但是，因为$f(x)$不是一个$n$次多项式，$f(x)\neq p_n(x)$，因此$p_n(x)$只是$f(x)$的一个逼近式，利用$p_n(x)$可以在某种准确度内算出$f(x)$。
对于给定$\mathscr{X}$中的$x$与给定的$n$时的差：

$r_n(x)=f(x)-p_n(x)$ $r_n(x)=f(x)-f(x_0)-\frac{f'(x_0)}{1!}(x-x_0)-\cdots-\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n \tag{7}$

就是很重要的事情了。

我们尝试用一个表达式替换$r_n(x)$，假设$f(x)$除了做成多项式$p_n(x)$所需要的条件外，还满足在$\mathscr{X}$内有直到$(n+1)$阶为止的各项导数：

$f'(x),f''(x),\ldots,f^{(n)}(x),f^{(n+1)}(x)$

现在我们将$\mathscr{X}$以内的变量$x$固定下来，将常数$x_0$换成变量$z$，就得到了一个辅助函数：

$\varphi(z)=f(x)-f(z)-\frac{f'(z)}{1!}(x-z)-\cdots-\frac{f^{(n)}(z)}{n!}(x-z)^n$

自变量$z$在区间$[x_0,x]$（假设$x_0\lt x$）上变动，在这个区间上$\varphi(z)$是连续的，并且有：

$\varphi(x_0)=r_n(x),\varphi(x)=0\tag{8}$

此外，在$(x_0,x)$存在导数：

$\begin{aligned} \varphi'(z)=&-f'(z)-[\frac{f''(z)}{1!}(x-z)-f'(z)]-[\frac{f'''(z)}{2!}(x-z)^2-\frac{f''(z)}{1!}(x-z)] \\ &-\cdots-[\frac{f^{(n+1)}(z)}{n!}(x-z)^{n}-\frac{f^{(n)}(z)}{(n-1)!}(x-z)^{n-1}] \\ \end{aligned}$

化简得到：

$\varphi'(z)=-\frac{f^{(n+1)}(z)}{n!}(x-z)^{n}\tag{9}$

附注

上述求导过程基于：
$(\frac{f^{(i)}(z)}{i!}(x-z)^i)'=\frac{f^{(i+1)}(z)}{i!}(x-z)^i-\frac{f^{(i)}(z)}{(i-1)!}(x-z)^{i-1}$
下面证明这一结论（专门留给像我这样不会求导的同学）

根据积法则：
$(\frac{f^{(i)}(z)}{i!}(x-z)^i)'=[(\frac{f^{(i)}(z)}{i!})'(x-z)^i+\frac{f^{(i)}(z)}{i!}[(x-z)^i]']$
因为根据链式法则$f(g(x))’=f’(g(x))\cdot g’(x)$，故有：
$\begin{aligned} (\frac{f(x)}{g(x)})'&=(f(x)\cdot\frac{1}{g(x)})' \\ &=f'(x)\cdot\frac{1}{g(x)}+f(x)(\frac{1}{g(x)})' \\ &=\frac{f'(x)}{g(x)}+f(x)\cdot\frac{1}{g^2(x)}\cdot g'(x) \\ &=\frac{f'(x)g(x)+f(x)g'(x)}{g^2(x)} \end{aligned}$
因此：
$(\frac{f^{(i)}(z)}{i!})'=\frac{f^{(i+1)}(z)\cdot i!-f^{(i)}(z)\cdot0}{(i!)^2}=\frac{f^{(i+1)}(z)}{i!}$
而：
$[(x-z)^i]'=i(x-z)^{i-1}\cdot(0-1)=-i(x-z)^{i-1}$
故：
$\begin{aligned} (\frac{f^{(i)}(z)}{i!}(x-z)^i)'&=[(\frac{f^{(i)}(z)}{i!})'(x-z)^i+\frac{f^{(i)}(z)}{i!}[(x-z)^i]'] \\ &=\frac{f^{(i+1)}(z)}{i!}(x-z)^i+\frac{f^{(i)}(z)}{i!}(-i(x-z)^{i-1}) \\ &=\frac{f^{(i+1)}(z)}{i!}(x-z)^i-\frac{f^{(i)}(z)}{(i-1)!}(x-z)^{i-1} \end{aligned}$
Q.E.D.

若再取一个任意函数$\psi(x)$，它在$[x_0,x]$上连续，在$(x_0,x)$内存在不等于$0$的导数。
那么根据柯西公式得到：

$\frac{\varphi(x_0)-\varphi(x)}{\psi(x_0)-\psi(x)}=\frac{\varphi'(c)}{\psi'(c)}$

其中$c\in(x_0,x)$，即$c=x_0+\theta(x-x_0)(0\lt\theta\lt1)$。
考虑$(8)(9)$两式，有：

$\frac{r_n(x)-\varphi(x)}{\psi(x_0)-\psi(x)}=\frac{\frac{-f^{(n+1)}(c)}{n!}(x-c)^n}{\psi'(c)}$

故：

$r_n(x)=-\frac{\psi(x_0)-\psi(x)}{\psi'(c)}\cdot\frac{f^{(n+1)}(c)}{n!}(x-c)^n\tag{10}$

接下来我们任意选择$\psi(z)$可得出一些形式的泰勒展开后的余项，本文仅仅介绍拉格朗日余项。
将$\psi(z)$选成：

$\psi(z)=(x-z)^{n+1}$

它满足上述的条件，且有：

$\psi(x_0)=(x-x_0)^{n+1},\psi(x)=0,\psi'(c)=-(n+1)(x-c)^n$

代入$(10)$中可得：

$r_n(x)=\frac{f^{(n+1)}(c)}{(n+1)!}(x-x_0)^{n+1}\tag{11}$

考虑$(7)(11)$两式，函数$f(x)$可以表示为：

$f(x)=f(x_0)+\frac{f'(x_0)}{1!}(x-x_0)+\cdots+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+\frac{f^{(n+1)}(c)}{(n+1)!}(x-x_0)^{n+1}\tag{12}$

它与多项式的泰勒公式相比刚好多出一个余项。
余项式$(11)$称作拉格朗日余项，它很像泰勒公式接下来的一项，只是将$(n+1)$阶导数不取于$x_0$处，而取于$x_0$与$x$间某一中值$c$处。
公式$(12)$称作带有拉格朗日余项的泰勒公式，其形式简单易用，但在个别情况下不太适用，就需要用到略微复杂的其他形式（如：柯西型余项，佩亚诺型余项，积分型余项）。