C++

概述 MultiGenerator 作为早年我的试验项目，已不再适合于实际使用。如果想要生成数据，请使用性能更高且更简单的 Rust 实现：data-gen-rs。 MultiGenerator 是一个为 OI 而生的多线程并行数据生成库，基于 C++ 17，使用面向对象和泛型等 Morden C++ 高级特性，只需要添加最少的额外代码，就可以获得最高的性能。以下是一个能够指定数据范围的 A + B Problem 数据生成器的示例代码： #include <random> #include <MultiGenerator.hpp> using MultiGenerator::DataConfig; using MultiGenerator::GeneratingTask; using MultiGenerator::SolutionTask; using MultiGenerator::NormalTemplate; using MultiGenerator::entry; using MultiGenerator::testcase; /** 指定数据生成器，仅需继承一个抽象类和实现一个成员函数 */ class AddGenerator : public GeneratingTask { private: void generate(std::ostream &data, const DataConfig &config) override { /** DataConfig 为配置信息，可以用于储存数据范围等元信息 */ auto minValue = std::stoi(config.get("minValue").value()); auto maxValue = std::stoi(config.get("maxValue").value()); std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution<> dist(minValue, maxValue); /** 像 cout 一样输出生成结果 */ data << dist(gen) << " " << dist(gen) << std::endl; } }; /** 指定数据求解器，也仅需继承一个抽象类和实现一个成员函数 */ class AddSolution : public SolutionTask { private: /** 假如你有标程，仅需要把程序用这个类包装起来，再把 main() 改为这个成员函数即可 */ void solve(std::istream &dataIn, std::ostream &dataOut, const DataConfig &) override { int a, b; /** 像 cin 一样读入数据 */ dataIn >> a >> b; /** 像 cout 一样输出答案 */ dataOut << a + b << std::endl; } }; int main() { constexpr int MAX_THREAD_COUNT = 8; constexpr int MAX_TESTCASE_COUNT = 20; constexpr char PROBLEM_NAME[] = "add"; /** 创建一个题目生成模板，指定数据文件名为 add#....

二分图 定义 如果一个图 $G=(V,E)$ 中的结点可以被分为两个部分，且两个部分之内的点互相没有连边，则称这种图为二分图。如果每个结点的度数相等且都为 $k$，则称这种二分图为 $k$ - 正则二分图。 判断 对图的结点进行黑白染色，相连的结点染不同的颜色，若最后满足每条边的两个端点颜色不相同，则这个图是二分图。树也是二分图。 染色 这里的染色不同于判断的染色，它指的是对边进行染色。若染 $k$ 种颜色，则称其为二分图的 $k$ 染色。 对于一个 $k$ - 正则二分图来说，它一定可以被 $k$ 染色，而对于一般的二分图，若其最大度数为 $k$，则它也可以被 $k$ 染色。 匹配 在二分图的边集中选出一个非空子集，且这个非空子集内没有两条边连接了一个相同的端点，则这个非空子集被称为二分图的一个匹配，同样对于一般图也有类似的概念。 若一个匹配的所含的边数最大，则称这个匹配为最大匹配。 若二分图两边的结点个数相同，且存在一个匹配满足其中的边连接了所有的点，则这个匹配被称为这个二分图的完美匹配或者完备匹配。 若每条边有边权，且一个匹配的所含的边的权值和最大，则这个匹配被称为这个二分图的最大权匹配。 匈牙利算法 交替路 假设在二分图最大匹配的过程中，已经找到了一些边作为一个匹配，则一条交替路就是一个匹配边和非匹配边交替连接组成的简单路径。 根据二分图的定义，假设一条交替路的起点在左边，且第一条边是匹配边，则这条交替路中的匹配边一定都是从左边到右边，而非匹配边一定是从右边到左边。 交替路上的结点最多连接一条匹配边和一条非匹配边，所以如果把交替路上的匹配边变为非匹配边，非匹配边变为匹配边，则仍然满足条件，也就是交替路边集的匹配边集的补集也可以是匹配。 增广路 匈牙利算法的核心就是找增广路，这条增广路是一条交替路。每次增广从左边开始，第一条边是非匹配边，最后一条边也是非匹配边，根据上文的描述，这样的路径的边数为奇数，非匹配边个数比匹配边个数多 $1$，若把匹配边与非匹配边反转，则反转后的边集仍然是一个合法的匹配，且比原来的匹配的边数多了 $1$。如果能找到一条这样的增广路，则此次增广成功。 具体来说，比如一个左边的结点 $x$ 找到了一个右边的结点 $y$，它没有与其他左边的结点匹配过，则 $e(x,y)$ 可以作为一个匹配边，反转边集前，有 $1$ 条匹配边，$0$ 条非匹配边，增广成功。 如果右边的结点 $y$ 已经有匹配了，那么就可以让原来 $y$ 的匹配 $x'$ 新找一个点 $y'$，如果能够找到这个 $y'$，那么 $e(x',y')$ 成为一个匹配边，$y$ 就无需和 $x'$ 匹配了，也就是说 $y$ 已经变为了一个没有匹配的点，$x$ 就可以与 $y$ 匹配了。如果 $x'$ 找不到 $y'$，那么 $x'$ 就要保持原样，和 $y$ 匹配，那么 $x$ 就不可以和 $y$ 匹配，只能继续寻找下一个可能的结点。...

莫比乌斯反演可以用于优化一类式子的计算。 莫比乌斯函数 定义 莫比乌斯函数的定义如下： $$ \mu(n)= \begin{cases} 0 & \exists\ p^2 \mid n \wedge p>1\\\\ (-1)^k & n=\prod_{i=1}^{k} p_i \end{cases} $$ 也就是说，如果 $n$ 含有平方约数，则 $\mu(n)=0$，否则 $\mu(n)=(-1)^k$，其中 $k$ 为 $n$ 中的本质不同的质约数个数。 性质 积性函数 $\mu(n)$ 为积性函数，证明如下： 设 $a,b$ 满足 $\gcd(a,b)=1$。 若 $a,b$ 其中一个数含有平方约数，则它们的乘积也一定含有平方约数，此时它们的莫比乌斯函数值都为 $0$，即 $\mu(ab)=\mu(a)\mu(b)=0$。 否则 $a,b$ 都不含有平方约数，则设它们的质约数个数分别为 $k_a,k_b$，则 $\mu(a)=(-1)^{k_a},\mu(b)=(-1)^{k_b}$，因为满足 $\gcd(a,b)=1$，故 $ab$ 的质约数个数为 $k_a+k_b$，$\mu(ab)=(-1)^{k_a+k_b}=(-1)^{k_a}(-1)^{k_b}=\mu(a)\mu(b)$。 Q.E.D. 与常数函数的卷积 这个性质十分重要，是反演的基础。这个性质可以写成 $I * \mu= \epsilon$，或者： $$ \sum_{d\mid n}I(\frac{n}{d})\mu(d)=\epsilon(n) $$ 经常简记为： $$ \sum_{d\mid n} \mu(d) = [n=1] $$ $\epsilon$ 是 Dirchlet 卷积的单位元函数。...

解各种同余方程是同余问题的一个重要部分，本文介绍各种同余方程的求解方法。 二元线性不定方程 形式 不定方程的范围很广泛，只要没有确定的解的方程都可以叫不定方程。本文主要讨论数论中的不定方程。 $$ ax+by=c\ (a,b,c,x,y\in \mathrm{Z}) $$ 形如上面这种形式，满足各项的系数和解均为整数的方程就是数论中的不定方程。 求解 Theorem 1：$\forall a, b \in \mathrm{Z}$，一定存在 $x,y\in \mathrm{Z}$，使得 $ax+by=\gcd(a,b)$。 这个定理又叫做裴蜀定理，根据这个定理，可以得出不定方程 $ax+by=c$ 有解的充要条件就是 $\gcd(a,b)\mid c$。记 $d=\gcd(a,b)$，则我们可以先求出 $ax'+by'=d$ 的解，再令 $x=\frac{c}{d}x',y=\frac{c}{d}y'$，就得出原方程的一组解。 求 $x',y'$ 的过程可以用扩展欧几里得算法，即 exgcd 解决。 Theorem 2：若 $\gcd(a,b)=1$，且 $x_0,y_0$ 是方程 $ax+by=c$ 的一组解，则该方程的通解为 $x=x_0+kb,y=y_0-ka$，其中 $k\in \mathrm{Z}$。 换句话说，$x,y$ 这两个解是具有周期性的。根据这个定理，我们知道一定有一个 $x\in [0,b)$，而对于方程 $ax+by=c$，则一定有一个 $x\in [0,\frac{b}{\gcd(a,b)})$，由此可以求一个不定方程的一个元的最小非负整数解，具体地，假设知道了一个解 $x_0$，则最小非负整数 $x=(x_0 \bmod m + m) \bmod m$，其中 $m=\frac{b}{\gcd(a,b)}$。 总结一下，求解二元线性不定方程 $ax+by=c$ 的流程如下： 求出 $ax+by=\gcd(a,b)$ 的一组解 $x',y'$，并根据 $\gcd(a,b)\mid c$ 判断方程有无解 令 $x=\frac{c}{\gcd(a,b)}x',y=\frac{c}{\gcd(a,b)}y'$，$x,y$ 为 $ax+by=c$ 的一组解 若需要求 $x$ 的最小非负整数解，则将 $x=(x_0 \bmod m + m) \bmod m$ 作为最终的答案，其中 $m=\frac{b}{\gcd(a,b)}$ 线性同余方程 形式 $$ ax \equiv c \pmod{p} $$ 形如这样的方程，就被称线性同余方程。...

Burnside 引理和 Pólya 定理主要用于解决计算本质不同方案数的计数问题。 群论 基本定义 群可以看成是一个由集合和某个二元运算组成的二元组 $(S,\cdot)$，这里的 $\cdot$ 就代表一个二元运算，这个二元运算需要满足结合律、存在单位元和逆元。群有很多的种类，比如置换群、循环群、矩阵群等，其中置换群就是我们接下来要介绍的。 性质 若一个二元组 $(S,\cdot)$ 是群，则它满足以下性质： 封闭性：$\forall x,y\in S$，若 $z=x\cdot y$，则 $z\in S$ 结合律：$\forall x,y,z\in S$，$(x\cdot y)\cdot z=x\cdot (y \cdot z)$ 单位元：存在唯一一个元素 $e \in S$ 满足 $\forall x \in S$，$e\cdot x=x$ 逆元：$\forall x \in S$，都可以找到唯一一个元素 $x^{-1}$ 满足 $x \cdot x^{-1} = e$，这个元素称为 $x$ 的逆元 举一个简单的例子，$(\mathrm{Z},+)$ 就是一个群，无论取哪两个元素进行加法运算，结果仍然是整数；加法满足结合律；单位元 $e = 0$；任意一个元素 $x$ 的逆元 $x^{-1} = -x$。 置换与置换群 置换的基本定义 顾名思义，置换群就是置换组成的群。置换可以看成一个有限集合到自身的双射，具体一点，假设有两个长度相同的集合 $p,q$（这里假设集合可以有序），则置换 $f$ 作用于 $p$ 就是生成一个新的集合 $p'$，满足 $p'_i=p\_{q_i}$。...

欧拉函数 $\varphi(n)$ 是一个重要的数论函数，它表示 $[1, n]$ 中与 $n$ 互质的数的个数。 欧拉函数性质 积性函数 积性函数的定义是：如果一个函数 $f(n)$ 满足 $\gcd(a,b)=1$ 时 $f(ab)=f(a)f(b)$，则 $f(n)$ 为积性函数。 若无需 $\gcd(a,b)=1$ 就有 $f(ab)=f(a)f(b)$，则它为完全积性函数。 $$ n = \prod p_i^{c_i}\\\\ f(n) = \prod f(p_i^{c_i}) $$ 一般来说，各种积性函数都是可以使用欧拉筛计算出来的，尽管方法各不相同。 $\varphi(n)$ 也是积性函数，证明就省略了。 计算公式 因为 $\varphi(n)$ 是积性函数，所以我们可以先研究 $\varphi(p^k)$ 怎么计算。$p^k$ 的约数有 $1, p, p^2, \dots, p^k$，而 $p^2, \dots, p^k$ 都含有 $p$ 这个约数，如果一个数不与 $p^k$ 互质，则一点有 $p$ 这个约数，我们只有知道小于等于 $p^k$ 的数中 $p$ 的倍数有多少即可。由此得出 $\varphi(n) = p^k - \frac{p^k}{p} = p^k - p^{k-1}=p^k\frac{p-1}{p}$。...

拉格朗日插值是众多插值算法中的一种，插值是通过一些点来求出过这些点的多项式函数的过程。 算法思想 构造函数 给出 $n + 1$ 个点 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n),(x_{n+1},y_{n+1})$，要求出过这些点的 $n$ 次多项式函数（也称该函数的度为 $n$），先考虑对每个点构造一个函数，第 $i$ 个点的函数为 $f_i(x)$，满足： $$ f_i(x) = \begin{cases} y_i & x = x_i\\\\ 0 & x \ne x_i \end{cases} \ (x\in \\{x_1,x_2,\dots,x_n,x_{n+1}\\}) $$ 最后将这些函数组合为最终的函数： $$ f(x) = \sum_{i=1}^{n+1}f_i(x) $$ 接下来就是找到一种合适的形式来表示 $f_i(x)$ 的分段规定，可以让 $f_i(x)$ 含有一些因式，满足 $x=x_j,j\ne i$ 时，其值为 $0$，$x=x_i$ 时，其值为 $y_i$。显然下面这种满足条件： $$ f_i(x) = y_i \prod_{i\ne j} \frac{x-x_j}{x_i-x_j} $$ 所以最终的 $f(x)$ 的解析式为： $$ f(x) = \sum_{i=1}^{n + 1} y_i \prod_{i\ne j} \frac{x-x_j}{x_i-x_j} $$ 求单个函数值的时间复杂度是 $\Theta(n^2)$。...

高斯消元主要用于求解线性方程组的解，同时可以解决某些有后效性的 DP 问题， 算法思想 增广矩阵 为了更方便地求解方程组，可以将系数和常数项放入矩阵，接下来就可以用一些矩阵的操作来消元了。 比如有一个方程组如下： $$ \begin{cases} 3x+2y+3z=10\\\\ 3x+y+4z=12\\\\ x+y+z=4 \end{cases} $$ 我们可以这么用矩阵表示: $$ \begin{bmatrix} 2 & 2 & 3 \\\\ 3 & 1 & 4 \\\\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 10 \\\\ 12 \\\\ 1 \end{bmatrix} $$ 在理论分析和实现代码时，为了方便，通常把两个矩阵拼在一起，这个矩阵就是增广矩阵： $$ \begin{bmatrix} 2 & 2 & 3 & 10 \\\\ 3 & 1 & 4 & 12 \\\\ 1 & 1 & 1 & 1 \end{bmatrix} $$ 增广矩阵的第 $i$ 行代笔第 $i$ 个方程，第 $i$ 列表示第 $i$ 个未知数的系数或常数项，接下来用 $x_i$ 表示第 $i$ 个未知数。...