64位模数乘法

当模数是一个64位的整数时,乘法取模过程中就会溢出。

此时有两种解决方法

一种是采取与快速幂类似的思想,时间复杂度位$O(lg)$

边分治

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

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

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

CDQ分治与点分治的碰撞

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

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

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

密码Hello

Hello

更新主题

今天突然发现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)*B(x)\equiv1(mod \; x^n)$$

分治

考虑分治

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

FFT与NTT

快速傅立叶变换 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的应该都能看懂。。

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

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×