题意描述

洛谷链接

LibreOJ 链接

对于一个序列，定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入，在本题中请以题面中给出的定义为准。

一开始给定 \(n\) 个长度不一的正整数序列，编号为 \(1 \sim n\)，初始序列可以为空。这 \(n\) 个序列被视为存在，其他编号对应的序列视为不存在。

有 \(q\) 次操作，操作有以下类型:

• \(1 \ x \ y\)：在 \(x\) 号序列末尾插入数字 \(y\)。保证 \(x\) 号序列存在，且 \(1 \le x, y \le n + q\)。
• \(2 \ x\)：删除 \(x\) 号序列末尾的数字，保证 \(x\) 号序列存在、非空，且 \(1 \le x \le n + q\)。
• \(3 \ m \ x_1 \ x_2 \ x_m\)：将 \(x_1, x_2, \ldots, x_m\) 号序列顺次拼接，得到一个新序列，并询问其众数。如果不存在满足上述条件的数，则返回 \(-1\)。数据保证对于任意 \(1 \le i \le m\)，\(x_i\) 是一个仍然存在的序列，\(1 \le x_i \le n + q\)，且拼接得到的序列非空。注意：不保证 \(\boldsymbol{x_1, \ldots, x_m}\) 互不相同，询问中的合并操作不会对后续操作产生影响。
• \(4 \ x_1 \ x_2 \ x_3\)：新建一个编号为 \(x_3\) 的序列，其为 \(x_1\) 号序列后顺次添加 \(x_2\) 号序列中数字得到的结果，然后删除 \(x_1, x_2\) 对应的序列。此时序列 \(x_3\) 视为存在，而序列 \(x_1, x_2\) 被视为不存在，在后续操作中也不会被再次使用。保证 \(1 \le x_1, x_2, x_3 \le n + q\)、\(x_1 \ne x_2\)、序列 \(x_1, x_2\) 在操作前存在、且在操作前没有序列使用过编号 \(x_3\)。

假定 \(C_l = \sum l_i\) 代表输入序列长度之和，\(C_m = \sum m\) 代表所有操作 \(3\) 需要拼接的序列个数之和；对于所有测试数据，保证 \(1 \le n, q, C_m, C_l \le 5 \times {10}^5\)。

题意描述

洛谷链接

LibreOJ 链接

设 \(d(x)\) 为 \(x\) 的约数个数，给定 \(n, m\)，求

\[ \sum_{i = 1}^n\sum_{j = 1}^m d(ij) \]

对于所有的数据，\(1 \leq N, M \leq 50000,\ 1 \leq T \leq 50000\)。

题意描述

洛谷链接

给定 \(N, M\)，求 \(1 \leq x \leq N\)，\(1 \leq y \leq M\) 且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对。

数据范围：\(T = 10^4\)，\(N, M \leq 10^7\)。

题意描述

洛谷链接

对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a \le x \le b\)，\(c \le y \le d\)，且 \(\gcd(x,y) = k\)，\(\gcd(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。

对于 \(100\%\) 的数据满足：\(1 \le n,k \le 5 \times 10^4\)，\(1 \le a \le b \le 5 \times 10^4\)，\(1 \le c \le d \le 5 \times 10^4\)。

莫比乌斯函数

了解莫比乌斯反演前，我们先要了解莫比乌斯函数。记 \(\mu(n)\) 为莫比乌斯函数，\(n\) 可被分解质因数为 \(n = \prod_{i = 1}^{m}{ {p_i}^{c_i} }\) 定义如下：

\[ \mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exists i \in [1, m], c_i > 1 \\ (-1)^m & \forall i \in [1, m], c_i = 1 \\ \end{cases} \]

形式化地解释一下：

• 当 \(n = 1\) 时，\(\mu(n) = 1\)；
• 当 \(n\) 存在至少一个出现次数大于等于两次的质因子时，\(\mu(n) = 0\)；
• 当 \(n\) 的所有质因子仅出现过一次，且 \(n\) 有奇数个质因子时，\(\mu(n) = -1\)；
• 当 \(n\) 的所有质因子仅出现过一次，且 \(n\) 有偶数个质因子时，\(\mu(n) = 1\)。

题意描述

洛谷链接

有一次，HKE 和 LJC 在玩一个游戏。

游戏的规则是这样的：LJC 在纸上写下两个长度均为 \(n\) 的数列 \(a\) 和 \(b\)，两个数列一一对应。HKE 每次可以找两个相邻的数 \(a_i\) 和 \(a_{i + 1}\)，如果它们两个不互质，HKE 可以选择得到 \((b_i + b_{i + 1})\) 分，然后擦掉 \(a\) 和 \(b\) 位置上的第 \(i, i + 1\) 个数，并把两个序列重新按顺序编号。当所有相邻的数互质时，游戏结束。

HKE 想知道他最大得分是多少。

题意描述

洛谷链接

LibreOJ 链接

小豆现在有一个数 \(x\) ，初始值为 \(1\) 。 小豆有 \(Q\) 次操作，操作有两种类型:

• 1 m： \(x = x \times m\) ，输出 \(x \bmod M\) ；

• 2 pos： \(x = x /\) 第 \(pos\) 次操作所乘的数（保证第 \(pos\) 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），输出 \(x\bmod M\) 。

题意描述

洛谷链接

给你一棵 \(n\) 个点的树，点带权，对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。

题意描述

HydroOJ 链接

打开了黑魔法师 Vani 的大门，队员们在迷宫般的路上漫无目的地搜寻着关押 applepi 的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为 \(k\) 的包包。

擂台赛一共有 \(n\) 项挑战，各项挑战依次进行。第 \(i\) 项挑战有一个属性 \(a_i\)，如果 \(a_i \ge 0\)，表示这次挑战成功后可以再获得一个容量为 \(a_i\) 的包包；如果 \(a_i=-1\)，则表示这次挑战成功后可以得到一个大小为 \(1\) 的地图残片。地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把获得的所有的地图残片都带走（没有得到的不用考虑，只需要完成所有 \(n\) 项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。并且他们至少要挑战成功 \(l\) 次才能离开擂台。

队员们一筹莫展之时，善良的守卫者 Nizem 帮忙预估出了每项挑战成功的概率，其中第 \(i\) 项挑战成功的概率为 \(p_i\%\)。现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。

题意描述

HydroOJ 链接

求一个有 \(n\) 的元素的可重数集 \(\{a_i\}\) 的子集的算术和的异或和。

数据范围：\(a_i > 0\)，\(1 < n < 1000\)，\(\sum a_i \le 2000000\)。