算法原理 首先将 s 处理为 #a#b#c#b#a# 的形式，方便同时统计长度为奇数或偶数的回文串。 设 d[i] 表示以 s_i 为对称中心所能扩展出的回文串个数，而manacher可以在线性时间内求出 d[1]\do…

前言 该算法用于寻找链表中环的入口以及环的长度，在算法竞赛中可用于寻找序列的循环节。 算法推导 设定两个指针tortoise和hare，一开始都在起点，每次tortoise移动1步，hare移动2步。 当tortoise…

前言 矩阵树定理可以统计无向图的生成树个数或所有生成树权值之和，以及有向图的根向/叶向树形图个数或所有树形图权值之和 其中，一个生成树/树形图的权值定义为其所有边的边权之积 p.s. 以下内容均默认可以有重边（视为不同的…

前言 扩展Lucas定理适用于大数组合数取模，且模数不一定为质数的情况 求解 Step 1 若 n,m 为非负整数，n\ge m，p 为任意正整数。现在要求的是 C_n^m\bmod p 首先将 p 分解为质因子的幂之积…

定义 对于非负整数 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）适用于求解模线性方程组，且模数不一定两两互质的情况 求解 两个方程 先考虑只包含两个方程的模线性方程组： \begin{cases} x\equiv b_1\pmod{a_1}\\ x…

前言 中国剩余定理可以用来求「模线性方程组」的解，即： \begin{cases} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2}\\ \cdots\\ x\equiv b_n…

定义 若 ax\equiv 1\pmod{p}，则称 x 为 a 关于 p 的逆元，记作 a^{-1} 逆元存在的充要条件：a,p 互质，即 \mathrm{gcd}(a,p)=1 求解 exgcd求逆元 由于同余方程 …

定义 二元一次不定方程的形式为：ax+by=c，与同余方程 ax\equiv c\pmod{b} 等价 扩展欧几里得算法（exgcd） 该算法用于求解形如 ax+by=\mathrm{gcd}(a,b) 的不定方程 当 …