边分治用来解决一些点分治中一些解决不了的问题。

比如说点分治时有很多棵子树，合并这些信息时不能保证时间复杂度。

而边分治时最多只会有两棵子树，就可以很好地解决问题。

看到了[Noi2014]购票这道题目，发现了这种操作（为什么之前没想到呢。。。）

代码还没写过，先口胡一下

有根树上的DP，每个点只能从祖先转移。

今天突然发现icarus主题不知道什么时候更新了

搞了一会儿更新好了，感觉好看了不少

前后对比图：

跳进了这个坑。。。于是就开始自闭了。

还有许许多多关于二项式系数的东西没有写，以后会补的(?)

二项式系数

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$

严格一点的定义：

$$
\binom{n}{m}=\begin{cases}
\frac{n!}{m!(n-m)!} & 整数m\geq 0\
0 & 整数m<0
\end{cases}
$$

结论

设$f(x)$是任意一个具有如下性质且在一个实数区间连续的单调递增函数且

$$f(x)=整数\to x=整数 $$

只要$f(x),f(\lfloor x \rfloor), f(\lceil x \rceil)$有定义，那么就有

$$f(\lfloor x \rfloor)=\lfloor f(\lfloor x \rfloor) \rfloor 和 f(\lceil x \rceil)=\lceil f(\lceil x \rceil) \rceil$$

定义

我们说$B(x)$是$A(x)$在模$x^n$意义下的逆元则是满足

$$A(x)\ast B(x)\equiv1(mod \; x^n)$$

分治

考虑分治

假如我们已经知道在模$x^{\lceil \frac{n}{2} \rceil}$下$A$的逆$B’$

快速傅立叶变换 FFT

对于两个多项式

$$A(x)=\sum_{i=0}^{N-1}a_ix^i$$

$$B(x)=\sum_{i=0}^{N-1}b_ix^i$$

FFT可以在$O(nlgn)$的时间内求出

$$C(x)=A(x)*B(x)=\sum_{i=0}^{2(N-1)}c_ix^i$$

其中$c_i=\sum_{j=0}^ia_jb_{i-j}$

SAM

关于后缀自动机整个算法，在这了就不多说了，感觉别人写的都很好QAQ

可以去看看参考资料里的几篇文章，感觉学过OI的应该都能看懂。。

在这里我就写一下自己的理解和一些性质和应用

简介

Min_25筛用来求一个函数的前缀和

如果函数是积性函数就可以做，如果不是积性函数的话有一部分也是可以做的

算法过程就像是在模拟埃氏筛法

时间复杂度是$O(\frac{n^{\frac{3}{4}}}{log(\sqrt{n})})$，然而我并不会证