数学

Manacher+回文自动机 专题训练 数学

Manacher+回文自动机 专题训练

本来计划着刷完网络流马上去博弈论的,可是做了两道题之后发现有点做不动了,就先花了半天来复习字符串,顺便把之前的坑都填上。 BZOJ2342 [Shoi2011]双倍回文 这道题用回文自动机应该是比较简单。因为满足要求的1/2回文串节点一定在当前节点的fail指针指向的祖先中,所以只需要建出回文自动机···
BZOJ2115 [Wc2011] Xor 线性基+DFS 数学

BZOJ2115 [Wc2011] Xor 线性基+DFS

题目   给出一个无向图,求一条1-n的路径,使路径边权xor和最大。 首先,可以把一条简单路径和任意多个环拼在一起,形成一条题目所求的路径。接着,对于任意一条简单路径,都可以和一些环的权值异或在一起,达到其他简单路径的效果。所以,我们只需找出任意一条简单路径,找到所有的环,再把环上的xo···
[深坑] FFT 快速傅里叶变换 数学

[深坑] FFT 快速傅里叶变换

个人认为,现在学这玩意还有点早,但是不打(抄)打(抄)板(标)子(程),以后再复习这玩意就会有点吃力,所以现在发一个刚打的板子(虽然只是停留在“感性理解”和“明白原理”的层面上)。另外有篇blog写的很好,思路很清楚,一并备份。 Links: fft-ntt https://riteme.githu···