置顶CSP 复习


复习复习

Pollard-Rho


问题

同余


费马小定理 欧拉定理 扩展欧拉定理

复数


虚数我们定义 $i = \sqrt{-1}$ ,称 $i$ 为虚数单位。

分块


简介其实,分块是一种思想,而不是一种数据结构。从 NOIP 到 NOI 到 IOI,各种难度的分块思想都有出现。分块的基本思想是,通过对原数据的适当划分,并在划分后的每一个块上预处理部分信息,从而较一般的暴力算法取得更优的时间复杂度。分块的时间复杂度主要取决于分块的块长,一般可以通过均值不等式求出某

狄利克雷卷积与莫比乌斯函数


狄利克雷卷积 $f(x)$ 和 $g(x)$ 是定义在数论函数间的一种二元运算,可以定义为:

$$(f*g)(n) = \sum_{xy=n}f(x)g(x)$$ $$\Rightarrow\sum_{d \mid n}f(d)g(\frac{n}{d})$$

DLX


精确覆盖问题问题定义精确覆盖问题(英文:Exact Cover Problem) 是指给定许多集合 $S_i(1\leq i \leq n)$ 以及一个集合 $X$ ,求满足以下条件的无序多元组 $(T_1,T_2,\cdots,T_m)$:$\forall i , j \in [1,m] , T

欧拉函数


欧拉函数定义欧拉函数(Euler's totient function),即 $\varphi$,表示的是小于等于 $n$ 和 $n$ 互质的数的个数。$e.g. \ \ \ \varphi(1) = 1$当 $n$ 是质数的时候,显然有 $\varphi(n) = n - 1$。计算若在算数剧本

树形 DP


树形 DP,即在树上进行的 DP。由于树固有的递归性质,树形 DP 一般都是递归进行的。树形 DP 的架构首先,我们要把这个树建好,通常我们把读入的边建立双向的,即如果 $u$ 与 $v$ 相连,建立 $u \to v$ 以及 $v \to u$ 。来看一下树形 $\text$ 伪代码。void d

组合数学


加法原理若完成一件事的方法有 $n$ 类,其中第 $i$ 类的方法包括 $a_i$ 中不同的方法,且这些方式互不重合,则完成这件事共有 $a_1 + a_2 + a_3 + \cdots + a_n$ 种不同的方法。乘法原理若完成一件事的方法有 $n$ 个步骤,其中第 $i$ 步骤有 $a_i$ 中