算法原理 首先将 s 处理为 #a#b#c#b#a# 的形式,方便同时统计长度为奇数或偶数的回文串。 设 d[i] 表示以 s_i 为对称中心所能扩展出的回文串个数,而manacher可以在线性时间内求出 d[1]\do…
标签:学习笔记
【学习笔记】环检测算法 Floyd's Tortoise and Hare
前言 该算法用于寻找链表中环的入口以及环的长度,在算法竞赛中可用于寻找序列的循环节。 算法推导 设定两个指针tortoise和hare,一开始都在起点,每次tortoise移动1步,hare移动2步。 当tortoise…
【学习笔记】矩阵树定理
前言 矩阵树定理可以统计无向图的生成树个数或所有生成树权值之和,以及有向图的根向/叶向树形图个数或所有树形图权值之和 其中,一个生成树/树形图的权值定义为其所有边的边权之积 p.s. 以下内容均默认可以有重边(视为不同的…
【学习笔记】扩展Lucas定理(exLucas)
前言 扩展Lucas定理适用于大数组合数取模,且模数不一定为质数的情况 求解 Step 1 若 n,m 为非负整数,n\ge m,p 为任意正整数。现在要求的是 C_n^m\bmod p 首先将 p 分解为质因子的幂之积…
【学习笔记】Lucas定理
定义 对于非负整数 n,m 和素数 p,设 n,m 在 p 进制下的展开为: n=\sum_{i=1}^k n_ip^{k_i}\\m=\sum_{i=1}^k m_ip^{k_i}\\ 则有同余式: C(n,m)\eq…
【学习笔记】欧拉函数
定义 对于正整数 n,其欧拉函数为小于等于 n 的正整数中与 n 互质的数的个数,记为 \varphi(n) 性质与定理 基本性质 设 p 为任意素数,则有以下性质: \varphi(p)=p-1 \varphi(p^k…
【学习笔记】扩展中国剩余定理(exCRT)
前言 扩展中国剩余定理(exCRT)适用于求解模线性方程组,且模数不一定两两互质的情况 求解 两个方程 先考虑只包含两个方程的模线性方程组: \begin{cases} x\equiv b_1\pmod{a_1}\\ x…
【学习笔记】中国剩余定理(CRT)
前言 中国剩余定理可以用来求「模线性方程组」的解,即: \begin{cases} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2}\\ \cdots\\ x\equiv b_n…
【学习笔记】二元一次不定方程(exgcd)
定义 二元一次不定方程的形式为:ax+by=c,与同余方程 ax\equiv c\pmod{b} 等价 扩展欧几里得算法(exgcd) 该算法用于求解形如 ax+by=\mathrm{gcd}(a,b) 的不定方程 当 …