Q779’s Blog

洛谷P3846 [TJOI2007] 可爱的质数/【模板】BSGS 题解 题目链接：P3846 [TJOI2007] 可爱的质数/【模板】BSGS 题意： 给定一个质数 \(p\)，以及一个整数 \(a\)，一个整数 \(b\)，现在要求你计算一个最小的非负整数 \(k\)，满足 \(a^k \equiv b \pmod p\)。 输入格式： 仅一行，有 \(3\) 个整数，依次代表 \(p, a, b\)。 输出格式： 仅一行，如果有 \(k\) 满足该要求，输出最小的 \(k\)，否则输出 no solution。 数据范围： 保证 \(2\le a,b < p<2^{31}\)。 BSGS 是求模质数 \(p\)​ 意义下的解，ExBSGS 是求模任意数下的解。 这里求的解实际上并不是模意义下的 \(\log\) ，因为离散对数函数定义在 \(a\) 为原根的情况下 BSGS 全称 Baby Step,Giant Step，可以用于解决形如以下高次同余方程，其中 \(a,b,p\) 给出 \[ a^x\equiv b \pmod{p}\\ x^a \equi...

离散对数 在数论中，离散对数 (Discrete logarithm) 是基于原根的对数运算。 离散对数在一些特殊情况下可以快速计算，然而通常没有非常快速的方法来计算它们。（比如模质数时） 定义 设 \(a\) 为模 \(m\) 的原根，若 \(a^k \equiv b\pmod{m}\) ，则 \[ \log_ab\equiv k \pmod{m} \] 定义为以 \(a\) 为底模 \(m\)​​ 时的离散对数值。 解释 为什么只有原根为底才行呢？ 因为当 \(a\) 是模 \(m\) 的原根时，\(a^0,a^1\cdots a^{\varphi(m)-1}\) 在模意义 \(m\) 下两两不同 否则如果存在两个相同的，那么离散对数就会出现一对多的情况，所以只能用原根。 性质 \[ \log_abc\equiv \log_ab + \log_a c \pmod{\varphi(m)} \\[6pt]\log_ax^b\equiv b\log ax\pmod{\varphi(m)} \] 参考文献： [1] https://zhuanlan.zhihu.com/p/52...

洛谷P5810 [SCOI2004] 文本的输入 题解 题目链接：P5810 [SCOI2004] 文本的输入 题意： 人们在输入文本时，除了逐个输入这种方式外，还可以利用剪贴板进行复制，如果打入一个字母需要 \(1\) 的时间，将已输入的部分复制进剪贴板需要 \(5\) 的时间（Ctrl+A，Ctrl+C，再取消全选状态），将剪贴板的内容粘贴出来需要 \(2\) 的时间（Ctrl+V）。 如果我们不关心输入文本的内容，而只关心输入文本的长度，要输入一个长度不低于 \(n\) 的文本最少需要多少时间？ 请注意，数据范围与原题略有不同。 输入格式： 一个正整数 \(n\)，表示文本的长度。 输出格式： 一个正整数 \(t\)，表示需要的最短的时间。 数据范围： 对于 \(100\%\) 的数据，\(n\le 4\times 10^4\)。 考虑dp。设 \(f_i\) 表示花费为 \(i\) 的最大价值，转移有两种 第一种直接添加一个字符，即（这显然是 \(f_i\) 的下界） \[ f_i = f_{i-1} + 1 \] 第二种 copy 一次然后 paste 若干次，即...

洛谷P1748 H数 题解 题目链接：P1748 H数 题意： 所谓 \(H\) 数，是指只含有 \(2,3,5,7\) 这些质因数的数，如 \(630\) 是 \(H\) 数，而 \(22\) 不是。 现在要求输出第 \(n\) 个 \(H\) 数，即 \(H_n\) （为了方便起见将 \(H_1\) 定为 \(1\) ）。 已知 \(n\) 不超过 \(10000\)，最后数据在 int64 范围之内。 输入格式： 一行， \(n\) 。 输出格式： 一行，输出 \(H_n\)​ 。 虽说是 普及/提高− 的题，但是它的思路还是挺有意思的。 考虑dp，或者说考察 \(H_n\) 的递推方式。 \[ H_i=\min\{H_a\times 2,~H_b\times 3,~H_c \times 5,~H_d\times 7\} \] 其中 \(a,b,c,d\) 均满足特定形式，例如 \(H_{a-1}\times 2 \le H_i < H_a \times 2\) 。 一种暴力的转移方式是，枚举 \(j\) ，并钦定：例如当 \(j\) 满足 \(a\) 的条件时尝...

洛谷P1306 斐波那契公约数 题解 题目链接：P1306 斐波那契公约数 题意： 对于 Fibonacci 数列： \[ f_i = f_{i - 1} + f_{i - 2} + [i = 1] \] 请求出 \(f_n\) 与 \(f_m\) 的最大公约数，即 \(\gcd(f_n, f_m)\)。 输入格式： 一行两个正整数 \(n\) 和 \(m\) 。 输出格式： 输出一行一个整数，代表 \(f_n\) 和 \(f_m\) 的最大公约数。答案请对 \(10^8\) 取模。 数据范围： 保证 \(1 \leq n, m \leq 10^9\)。 结论1：\(\gcd(f_n, f_{n-1}) = 1\) 证明： \[ \gcd(f_n,f_{n-1}) = \gcd(f_{n-2},f_{n-1}) = \cdots = \gcd(f_1,f_2) = 1 \quad \square \] 结论2：\(f_{n + m} = f_{m+1}f_n + f_{m}f_{n-1}\) 证明：考虑归纳法。显然 \(n=m=1\) 时结论成立。设对于 \(n,m \le...

洛谷P9965 [THUPC 2024 初赛] 转化 题解 题目链接：P9965 [THUPC 2024 初赛] 转化 题意： 小 E 有 \(n\) 种颜色的球，其中第 \(i\) 种有 \(a_i\) 个。有两类工具，第一类可以把一个指定颜色的球变成一个任意颜色的球；第二类可以把一个指定颜色的球变成两个这种颜色的球。一个变化之后的球也可以通过工具产生新的变化。关于第 \(i\) 种颜色的第一类工具有 \(b_i\) 个，第二类工具有 \(c_i\) 个。小 E 想知道，如果每一个工具最多只能使用一次，那么对于每种颜色 \(i\)，第 \(i\) 种颜色的球最后最多能有多少个。以及，小 E 最后最多能有多少个球。 输入格式： 第一行一个正整数 \(n\)。 第二行 \(n\) 个整数，其中第 \(i\) 个表示 \(a_i\)。 第三行 \(n\) 个整数，其中第 \(i\) 个表示 \(b_i\)。 第四行 \(n\) 个整数，其中第 \(i\) 个表示 \(c_i\)。 输出格式： 第一行 \(n\) 个整数，其中第 \(i\) 个表示如果每个工具最多使用一次，那么小 E...

洛谷P2429 制杖题 题解 题目链接：P2429 制杖题 题意： 求不大于 \(m\) 的、质因数集与给定质数集有交集的自然数之和。 输入格式： 第一行，两个整数 \(n, m\)。 第二行，\(n\) 个整数，表示质数集内的元素 \(p_i\)。 输出格式： 一个整数，表示答案，对 \(376544743\) 取模。 数据范围： 测试点编号 规模 \(1 \sim 3\) \(n m \le {10}^7\) \(4 \sim 5\) \(n \le 2\)，\(m \le {10}^9\) \(6 \sim 7\) \(n \le 20\)，\(m \le {10}^8\) \(8 \sim 10\) \(n \le 20\)，\(m \le {10}^9\) 对于 \(100 \%\) 的数据，\(1 \le n \le 30\)，\(1 \le m \le {10}^9\)。 数据范围可能有点令人迷惑，我猜它是指测试点 \(1\sim 3\) 满足 \(n \le 30\) 。 记 \(S_i=\sum_{p_i \mid x \,\...

洛谷P4980 【模板】Polya 定理 题解 题目链接：P4980 【模板】Polya 定理 题意： 给定一个 \(n\) 个点，\(n\) 条边的环，有 \(n\) 种颜色。 给每个顶点染色，问有多少种本质不同的染色方案，答案对 \(10^9+7\) 取模 注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。 输入格式： 第一行输入一个 \(T\)，表示有 \(T\) 组数据 第二行开始，一共 \(T\) 行，每行一个整数 \(n\)，意思如题所示。 输出格式: 共 \(T\) 行，每行一个数字，表示染色方案数对 \(10^9+7\) 取模后的结果。 数据范围： \(1\le T \le 10^3, ~1 \le n \le 10^9\) 传送门：Pólya 定理 （在这篇文章里讲解了推导过程） 首先先把 Burnside 引理复习一下。 Burnside 引理 设 \(A,B\) 为有限集合，\(X\) 为一些从 \(A\) 到 \(B\) 的映射组成的集合（这可以视作直接染色）。 \(G\) 是 \(A\) 上的置换群，且 \(X\) 中的映射在 \(G...

Pólya 定理 Pólya 定理的中文名是波利亚计数定理。 传送门：洛谷P4980 【模板】Polya 定理 题解 （在这篇文章里会讲解 Pólya 定理 的运用） 置换 一个有限集合 \(S\) 到自身的双射称为 \(S\) 的一个置换。集合 \(S=\{a_1,a_2,\cdots,a_n\}\) 上的置换可以表示为 \[ \varphi=\left(\begin{array}{c} a_1, a_2, \ldots, a_n \\ a_{p_1}, a_{p_2}, \ldots, a_{p_n} \end{array}\right) \] 意为将 \(a_i\) 映射为 \(a_{p_i}\) ，其中 \(p_1,p_2,\cdots,p_n\) 是 \(1,2,\cdots,n\) 是一个排列。显然 \(S\) 上置换的总数为 \(n!\) 。 对于两个置换 \(f = \left(\begin{array}{c}a_1, a_2, \ldots, a_n \\a_{p_1}, a_{p_2}, \ldots, a_{p_n}\end{array}\right)\...

中国剩余定理 & 扩展 鉴于之前写的中国剩余定理依托构思，现在重写一篇。 中国剩余定理 中国剩余定理(CRT)可求解如下形式的一元线性同余方程组 \[ \begin{cases} x \equiv a_1\ \pmod{p_1} \\[6pt] x\equiv a_2\ \pmod{p_2} \\[6pt] \quad\vdots \\[6pt] x \equiv a_n\ \pmod{p_k}\end{cases} \] 其中 \(p_1,p_2,\cdots,p_k\) 两两互质。 板子题：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 算法原理很简单 计算 \(P = \prod p_i\) 记 \(m_i = \frac{P}{p_i}\) ，\(m_i^{-1}\) 为模 \(p_i\) 意义下的乘法逆元，求 \(c_i = m_im_i^{-1}\) 方程组的唯一解 \(x = \sum_{i=1}^{k}a_ic_i\pmod{P}\)​ 证明就不讲了，中国剩余定理主要还是流程比较难记（确信） 时间复杂度 \(\mathcal{O}(n \...

群论基础 在数学和抽象代数中，群论（Group Theory）主要研究叫做「群」的代数结构。 群的定义 在数学中，群（group）是由一种集合以及一个二元运算所组成的，符合「群公理」的代数结构。 一个群是一个集合 \(G\) 加上对 \(G\) 的二元运算。二元运算用 \(\cdot\) 表示，它结合了任意两个元素 \(a,b\) 同时形成了一个属于 \(G\) 的元素，记作 \(a\cdot b\) 。 群公理包含下属四个性质（有时会略去封闭性）。 若集合 \(G \ne \varnothing\) 和 \(G\) 上的运算 \(\cdot\) 构成的代数结构 \((G,\cdot)\)​ 满足以下性质： 封闭性：对于所有 \(G\) 中的 \(a,b\) ，运算 \(a \cdot b\) 的结果也在 \(G\) 中、 结合律：对于 \(G\) 中的所有 \(a,b,c\) ，等式 \((a\cdot b)\cdot c = a\cdot (b \cdot c)\) 成立 单位元（也称幺元）：\(G\) 中存在一个元素 \(e\) ，使得对于 \(G\) 中的每个元素 \...

公平组合游戏 经典的公平组合游戏有很多，包括取数游戏，31 点，以及 Nim 游戏等。 Nim 游戏 首先介绍什么是 Nim 游戏。有 \(n\) 堆物品，每堆有 \(a_i\) 个。 两个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人获胜。 例如，如果现在有 \(n=3\) 堆物品，而每堆分别有 \(2,5,4\) 个，那么可以取走第 \(1\) 堆中的 \(2\) 个物品， 局面就变成了 \(0,5,4\) ，或者也可以取走第 \(2\) 堆的 \(4\) 个物品，局面就变成了 \(2,1,4\) 。 如果现在的局面为 \(0,0,5\) ，甲取走了第 \(3\) 堆的 \(5\) 个物品，也就是取走了最后一个物品，甲获胜。 不过我相信会来看这篇文章的人大概都知道 Nim 游戏吧。 博弈图 & 状态 如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。 例如，如果节点 \((i,j,k)\) 表示局面为 \(i,j,k\) 时的状态，则我们可以画出下面的博弈图（部分） 定义 必胜状态 为先手必胜的状态（通...