洛谷2022七月月赛
A
题目描述
15B03 的座位非常拥挤，可以看成一张 $n\times m$ 的网格，每个小正方形 $(i, j)$ 代表一张桌子。
根据规定，考场上任何两张桌子不得相邻。这里相邻指含有 公共点。严格定义两张桌子 $(i, j)$ 和 $(i’, j’)$ 相邻当且仅当 $|i - i’|\leq 1$ 且 $|j - j’|\leq 1$。
布置考场的任务落在小 A 头上，他希望撤去最少的桌子满足上述要求。
小 A 认为这样太简单了，因此他添加了限制：在保证撤去桌子最少的前提下，最大化剩余每张桌子到距离它最远的桌子的距离之和。这里距离指 欧几里得 距离：桌子 $(a, b)$ 和 $(c, d)$ 的距离为 $\sqrt{(a - c) ^ 2 + (b - d) ^ 2}$。
平行时空中 15B03 的规模不尽相同：多组测试数据。
数据范围
- 测试点 #1（15 points）：$n, m$ 均为奇数。
- 测试点 #2（20 points）：$n = 1$。
- 测试点 #3（25 points）：$n = 2$。
- 测试点 #4（30 points）：$n$ 为奇数。依赖测试点 #1，#2。
- 测试点 #5（10 points）：无特殊限制。依赖测试点 #3，#4。
对于 $100%$ 的数据：
- $1\leq T\leq 57$。
- $1\leq n, m\leq 1064$。
Sol
第一问的答案是 $\left\lceil \dfrac {n + 1} 2 \right\rceil\left\lceil \dfrac {m + 1} 2 \right\rceil$。选择奇数行和奇数列的所有交点，可以使得每个 $2\times 2$ 的小正方形 $(2k - 1 / 2k, 2k - 1 / 2k)$ 都存在一个格子被选。当 $n$ 或 $m$ 是奇数时，边界处小正方形不满。这种讨论是平凡的。
这样的构造是上界，因为每个小正方形至多选出一个格子。
对于第二问，我们有如下构造：若横坐标为奇数则横坐标固定，若为偶数则当 $\leq \dfrac n 2$ 时选奇数行，否则选偶数行。对于纵坐标同理。这样，四个角均被占用，并且每个位置都取到了它所能贡献的最大值。证明方法是观察到每个 $2\times 2$ 的小正方形 $(2k - 1 / 2k, 2k - 1 / 2k)$ 当中只能恰好放一个，而恰好放的这一个取到了贡献的最大值，具体证明细节略去。
需要特判 $n = 2$ 或 $m = 2$ 的情况。
根据构造算答案即可，时间复杂度 $\mathcal{O}(nm)$。
据验题人反应，第二问难度较大。我们给第一问 $80$ 分以达到送分的目的。
参考代码
1 |
|
B
题目描述
小 A 有 $n$ 个 $2$ 的幂 $a_1, a_2, \cdots, a_n$。他要在这些数之间插入 $x$ 个异或运算符和 $y$ 个或运算符，组成一个表达式。保证 $x + y = n - 1$。
表达式越大，越有可能炸掉小 T 的博客。小 A 希望 从左往右 计算表达式时它的值最大。他想知道表达式最大可能的取值是多少，用二进制表示。他还希望你构造出这样的表达式，因为他懒得自己构造了。
若存在多组构造方案，输出任意一组。
多组测试数据。
数据范围
- 测试点 #1（10 points）：所有 $b_i$ 互不相等。
- 测试点 #2（20 points）：所有 $b_i$ 相等。
- 测试点 #3（30 points）：$n \leq 8$。
- 测试点 #4（25 points）：$n \leq 10 ^ 3$。依赖测试点 #3。
- 测试点 #5（15 points）：无特殊限制。依赖测试点 #1，#2，#4。
对于 $100%$ 的数据：
- $1\leq T\leq 20$。
- $1 \leq n \leq 2.5 \times 10 ^ 4$。
- $0 \leq x, y < n$，$x + y = n - 1$。
- $1\leq a_i < 2 ^ {2 ^ {2 ^ {2 ^ 2}}}$，即 $0\leq b_i < 65536$。
Sol
核心观察：或比异或更厉害。无论之前结果如何，只要在最后一次出现之前放上或就能让这一位变成 $1$。
对每个出现偶数次的位，在最后分配一个或就能变为 $1$。而出现奇数次的位就算不分配也是 $1$。
按位从大到小贪心，时间复杂度 $\mathcal{O}(n + V)$。
构造方案：在选择分配或的位的最后一次出现之前放上或。对于多于的或，从后往前填入所有空隙，容易发现不影响答案。剩余空隙放入异或。
参考代码
1 |
|
C
题目描述
小 A 一共有 $n$ 道题目没有补。评估后，他认为第 $i$ 题的难度为 $x_i$。
同时，他对自己的水平有评估值 $w$。他的水平会波动，因此 $w$ 会改变。
小 A 认为补难度和自己水平相近的题目（相差不超过 $b_1$）能带来收益 $inc$；相反，如果相差过大（相差超过 $b_2$）则浪费了时间，导致负收益 $dec$。因此，补第 $i$ 道题的收益为
$$
\begin{cases}
inc & |x_i - w| \leq b_1 \
0 & b_1 < |x_i - w| \leq b_2 \
dec & |x_i - w| > b_2 \
\end{cases}
$$
保证 $b_1 \leq b_2$ 且 $dec < 0 < inc$。
此外，小 A 有一些喜欢和讨厌的题。如果他没有补任何喜欢的题，或补了任何讨厌的题，就会不高兴。
小 A 将选择一段编号连续的题目进行补题。他希望补每道题的收益之和最大，并且补完题目后不会不高兴。请你告诉他这个最大值。
数据范围
- Subtask #1（7 points）：$n, q\leq 100$。
- Subtask #2（12 points）：$n, q\leq 500$。依赖 Subtask #1。
- Subtask #3（20 points）：$n, q\leq 4 \times 10 ^ 3$。依赖 Subtask #2。
- Subtask #4（25 points）：$w, x_i \leq 100$。
- Subtask #5（11 points）：$l = 1$，$h = 0$。
- Subtask #6（15 points）：$w, x_i \leq 10 ^ 5$。依赖 Subtask #4。
- Subtask #7（10 points）：无特殊限制。依赖 Subtask #3，#5，#6。
对于 $100%$ 的数据：
- $1\leq n, q \leq 10 ^ 5$。
- $0\leq w, x_i \leq 10 ^ 9$，$0\leq b_1 \leq b_2$ 且 $b_2$ 不大于 $w, x_i$ 上界的一半。
- $-10 ^ 4 \leq dec < 0 < inc \leq 10 ^ 4$。
- $1\leq l, il_i, ih_j \leq n$，$0 \leq h < n$，$l + h\leq 5$。
- 保证 $il$，$ih$ 递增，且一组询问每个下标至多出现一次。
Sol 1
考虑 $n, q \leq 500$。
容易发现，讨厌的题将序列割成若干连续段。连续段之间独立，因此单独考虑一个连续段。
对于当前区间 $[l, r]$，枚举其所有子区间，检查是否有喜欢的题落在其中并更新答案。
时间复杂度 $\mathcal{O}(n ^ 2q)$。
Sol 2
考虑 $n, q \leq 4\times 10 ^ 3$。
注意到对于每个位置，合法的右端点形成一段区间 $[l, r)$，从 $p$ 右边第一个喜欢的题 $l$ 开始，第一个讨厌的题 $r$ 结束。
将区间求和差分转化为端点最值，每次改变 $w$ 时暴力重新求前缀和，区间最值用线段树或 ST 表维护。
时间复杂度 $\mathcal{O}(nq \log n)$。
Sol 3
考虑 $x_i, w \leq 100$。
回答询问考虑直接枚举包含的喜欢的题，则对应的合法区间左右端点均为一段区间（被讨厌的题所限制）。区间查询前缀和最大最小值即可。
可能的 $w$ 仅有 $100$ 种取值。对每种 $w$ 的取值的对应序列建线段树维护之。
时间复杂度 $\mathcal{O}(nw + q\log n)$。
Sol 4
考虑正解。
当 $w$ 从 $1$ 增大到 $10 ^ 9$ 时，仅有 $\mathcal{O}(n)$ 次改变某个位置上的贡献的操作。
单点修改相当于对前缀和区间修改，将所有询问离线回答，用线段树维护区间加法区间最值。
时间复杂度 $\mathcal{O}(n(l\log n + h))$，空间复杂度线性。
参考代码
1 |
|
D
题目描述
以下是简化后的扫雷游戏规则：
- 定义连通为 八连通。
- 如果打开雷，所有雷全部爆炸，游戏结束。
- 如果打开空地，若其周围没有雷，则递归打开周围八个空地。
- 如图，点开任意红色框内方块均形成当前局面。
给定一张 $n\times m$ 的初始地图。小 A 决定搜出所有可能的局面，并找到最优鼠标点击顺序，从而速通这张地图。
为设置合适的数组大小，小 A 需要知道有多少种不同局面。对 $998244353$ 取模。
- 如果方块是雷，它有爆炸和未爆炸两种状态；如果方块是空地，它有打开和未打开两种状态。
- 两个局面不同，当且仅当存在方块状态不同。
- 保证周围无雷的空地形成不超过 $37$ 个连通块。
数据范围
设周围无雷的空地形成 $d$ 个连通块。
- Subtask #1（15 points）：$nm\leq 21$。
- Subtask #2（4 points）：地图中只有一个雷。
- Subtask #3（5 points）：$d = 0$。
- Subtask #4（6 points）：$d = 1$。
- Subtask #5（7 points）：$d = 2$。
- Subtask #6（8 points）：$d \leq 17$。依赖 Subtask #1，#2，#3，#4，#5。
- Subtask #7（9 points）：$d \leq 23$。依赖 Subtask #6。
- Subtask #8（16 points）：$d\leq 27$。依赖 Subtask #7。
- Subtask #9（17 points）：$d\leq 33$。依赖 Subtask #8。
- Subtask #10（13 points）：无特殊限制。依赖 Subtask #9。
对于 $100%$ 的数据：
- $1\leq n, m\leq 500$。
- $0\leq d\leq 37$。
- 不保证 地图中有雷或空地。
Sol 1
考虑 $d = 0$。
称「有雷空地」为周围有雷的空地，「无雷空地」为周围无雷的空地。
地图中没有无雷空地，每个空地的状态独立。设共有 $v$ 个有雷空地，根据乘法原理，答案为 $2 ^ {v + c}$，其中 $c$ 表示是否存在雷。
直接枚举空地及其周围空地求出 $v$，时间复杂度为 $\mathcal{O}(nm)$。
- 将不计入雷的局面数乘 $2$ 即可得到计入雷的局面数。
- 为叙述方便，下文中提到的局面均不计入点到雷的局面。
Sol 2
考虑 $d = 1$。
若空地周围存在无雷空地，当无雷空地打开时，该空地也同时打开。空地之间的状态并不独立。
设打开无雷空地形成的连通块将打开 $c$ 个有雷空地。当连通块未打开时，$v$ 个有雷空地的状态独立，有 $2 ^ v$ 种局面；当连通块打开时，$c$ 个有雷空地同时被打开，剩余 $v - c$ 个有雷空地的状态独立，有 $2 ^ {v - c}$ 种局面。
存在初始地图中没有雷的情况，此时答案为 $1$；否则答案为 $2\times (2 ^ v + 2 ^ {v - c})$。
容易 dfs 求出 $c$，时间复杂度为 $\mathcal{O}(nm)$。
Sol 3
考虑 $d = 2$。
将无雷空地形成的两个八连通块标上序号。设打开第 $i$ 个连通块时打开的有雷空地个数为 $c_i$。
讨论连通块的状态：
- 若连通块 $1, 2$ 都未打开，共有 $2 ^ v$ 种局面。
- 若连通块 $1$ 打开，连通块 $2$ 未打开，沿用 $d = 1$ 的做法，共有 $2 ^ {v - c_1}$ 种局面。
- 同理，若连通块 $2$ 打开，连通块 $1$ 未打开，共有 $2 ^ {v - c_2}$ 种局面。
- 若连通块 $1, 2$ 都打开，共有 $2 ^ {v - c_1 - c_2}$ 种局面。
分析第四种情况：直接按照这种思路写甚至过不了样例，因为两个连通块可能打开相同的有雷空地。如 $3 \times 3$ 的网格，左上角和右下角均为雷，则左下角和右上角的两个连通块同时打开中心空地。
设打开两个连通块时打开的相同有雷空地个数为 $e$。
在计算连通块 $1, 2$ 影响到的有雷空地个数时，上述结论多统计了 $e$ 个空地。此时应仅有 $c_1 + c_2 - e_{1, 2}$ 个有雷空地被打开，其余 $v - (c_1 + c_2 - e_{1, 2})$ 个有雷空地的状态独立。
答案为 $2\times (2 ^ v + 2 ^ {v - c_1} + 2 ^ {v - c_2} + 2 ^ {v - c_1 - c_2 + e})$。
dfs 求出 $c_i$ 与 $e$，时间复杂度为 $\mathcal{O}(nm)$。
Sol 4
考虑 $d \leq 15$。
设 $e_S$ 表示 恰好 同时被连通块集合 $S$ 打开的有雷空地数，可以 dfs 求出。
枚举打开的连通块集合 $S$，则答案为 $2 \times \sum\limits_{S} 2 ^ {S - \sum_{T\subseteq S} e_T}$。
直接枚举子集，时间复杂度 $\mathcal{O}(nm + 3 ^ d)$。
Sol 5
考虑 $d \leq 21$。
用 FMT 优化上式，时间复杂度 $\mathcal{O}(nm + d2 ^ d)$。
Sol 6
考虑 $d\leq 26$。
枚举子集的复杂度无法做到更优，考虑挖掘性质。
结论：一个有雷空地至多被两个连通块打开。
证明：
若一个有雷空地同向的两个角落的方块均为无雷空地，则这两个无雷空地一定在同一连通块，因为它们中间的方块是无雷空地。
一个有雷空地的上下和左右两个方块不可能均为无雷空地，否则该有雷空地为无雷空地。
根据上述限制，一个有雷空地最多被三个连通块打开，且其周围状态只能为：
1 | ? 0 ? |
其中 * 表示有雷空地，0 表示无雷空地，? 表示不重要的方块。
根据周围三个无雷空地的限制，中间的有雷空地为无雷空地，矛盾。得证。
因此 $e_S$ 仅在 $|S|\leq 2$ 处有值。在此基础上得以 $2 ^ d$ 求出 $f_S = \sum\limits_{T\subseteq S} e_T$。
对于 $f_S$，设 $p$ 为 $S$ 中编号最小的连通块，则 $f_S = f_{S \backslash p} + g_{p, S\backslash p} + e_$。$p$ 可以 lowbit 求得。
综上，时空复杂度 $\mathcal{O}(nm + 2 ^ d)$。
进一步地，可以将空间复杂度优化至 $\mathcal{O}(nm + d ^ 2)$。
时间复杂度仍然是 $\sum\limits_{i = 0} ^ {d - 1} 2 ^ i \times (d - i) \approx \mathcal{O}(2 ^ d)$。如果不放心，利用主定理求解 $T(n) = 2T(\frac n 2) + \log n$，解得 $T(n) = n$。
Sol 7
考虑 $d\leq 33$。
根据 Sol 6 的结论，将连通块抽象成点，令两个节点之间的权值为它们同时打开的空地数。若 $w(u, v) > 0$ 视 $u, v$ 之间连边。
每次枚举度数最大的节点的两种状态，考虑它对剩余节点的影响，并删掉该点。形成的连通块之间独立，分别暴搜。可以通过本题，但不会分析复杂度的算法不适合当正解。
我们给出优于 $2 ^ d$ 的 确定性 做法：
整张地图是二维平面，所以建出的图 $G$ 是平面图。根据四色定理，$G$ 的最大独立集 $I_{\max}$ 不小于 $\left\lceil \dfrac d 4\right\rceil$。最大独立集可以在 $2 ^ {\frac d 2}$ 或 $3 ^ {\frac d 3}$ 的时间内求得，以下做法摘自 pb 的《浅谈信息学竞赛中的独立集问题》学习笔记。
设 $f_S$ 表示点集 $S$ 上的最大独立集，令 $u$ 为 $S$ 中编号最大的节点，有 $f_S = \max(f_{S\backslash u}, f_{S\backslash u \backslash N(u)} + 1)$。因为前 $\dfrac d 2$ 层只有 $2 ^ {\frac d 2}$ 种递归的可能，后 $\dfrac d 2$ 层 $S$ 中最大节点不超过 $\dfrac d 2$，所以总共只有 $2 ^ {\frac d 2}$ 种状态，对这些状态记忆化即可做到 $\mathcal{O}(2 ^ {\frac d 2})$。
对 $V\backslash I_{\max}$ 做 Sol 6，$I_{\max}$ 内所有点的状态独立，可以 $\mathcal{O}(|I|)$ 考虑。
时间复杂度 $\mathcal{O}(2 ^ {d - I}I)$，空间复杂度 $\mathcal{O}(nm + d ^ 2)$。
Sol 8
考虑正解。
$I$ 中的点一旦独立，即可直接考虑贡献，不需要等到确定 $V\backslash I$ 所有节点的状态后再计算。因此，令 $I$ 的一个排列 $P = {p_1, p_2, \cdots, p_k}$ 的代价 $f(P)$ 为 $\sum\limits_{i = 1} ^ k2 ^ {|\cup_{j = 1} ^ iN(p_j)|}$，表示 $I$ 内所有节点以 $P$ 的顺序独立的时间代价：$p_i$ 独立时，$p_1\sim p_i$ 均独立，需要删去 $\cup_{j = 1} ^ {i} N(j)$ 内所有节点。
当 $I$ 较小时，枚举其所有排列并求出代价，否则随机足够多的排列使代价尽可能小。
得到最优排列 $P_b$ 后，求出对应删点顺序，并在对应时刻计算 $I$ 内某些节点的代价。
对于 $d = 37$ 而言，$I_{\max}$ 的最小值为 $10$，此时可以全排列求最小代价。在 $I_{\max}$ 卡到最小值的图中几乎不可能使得 $\min f(P)$ 大于 $2\times 2 ^ {d - I}$（出题人尝试构建这样的图，均无法保证 $I_{\max} = 10$）。若 $I$ 更大，则 $2 ^ {d - I}$ 变小，随机排列足够优秀。
复杂度可近似看做 $\mathcal{O}(2 ^ {d - I})$。
本题出题人即笔者。一开始的想法是从 windows 的经典游戏中获取灵感，出了两道月赛 D 难度的题目。一道关于蜘蛛纸牌，已经放在了 SWTR-07，另一道是本题。
本题考察了选手对乘法原理，容斥原理，状压 DP 和随机乱搞的运用能力，以及将问题从实际情境中抽离却不脱离实际情境的能力。本题将 $d$ 优化掉并获得更优时间复杂度的关键结论隐藏在背景当中。
最初正解的复杂度为 $d2 ^ d$，提交审核时，粉兔指出本题有无脑 FMT 做法，大幅拉低本题水准，故撤下。出题人抓住关键性质，不断思考后得到 $2 ^ d$ 做法。同时，出题人认为验题人 chenxia25 给出的 $d ^ 2$ 空间做法具有一定启发性，故二次加强了本题。
进一步地，验题人 asmend 给出复杂度玄学的暴搜做法，出题人实现后发现效率惊人。不仅因为题目的实际意义限制了造出强的数据非常困难，而且 $G$ 是平面图。
对于完全图而言暴搜不可行，但 $G$ 甚至不存在 $K_5$ 和 $K_{3, 3}$，所以暴搜本身复杂度可能就是正确的，加上一点随机化难以卡掉。
出题人请教 EI 后，他指出可以通过删去最大独立集以外的所有顶点实现较多节点的独立。结合平面图四色定理（最大独立集不小于点集的四分之一）与 $2 ^ {\frac n 2}$ 求解一般图最大独立集，出题人得到本题正解的基本思路。
出题人尝试卡掉暴力无果，实现 Sol 7 后发现速度太慢，无法通过 $d = 37$ 且 $I$ 卡到最小值的数据。尝试优化后得到最终正解。
出题人实现的基于随机化的最优秀暴力需要 2.1s，而 Sol 8 在出题人造出的最劣数据下仅需要 1.6s。因为难以估计 Sol 8 的复杂度上界，所以出题人将时间限制设为 3s。
也许这是第一次四色定理和 $2 ^ {\frac n 2}$ 最大独立集被应用在正经 OI 题当中。因为这一点，出题人认为本题是一道非常新颖有趣的问题，可惜暴力搜索可以通过。
单论本题正解，其难度堪比 Div.1 C 或 D。出题人将其放在 Div.2 D / Div.1 B 的位置，因为暴力搜索被定位为 intended solution。按照其难度判断，本题放在 2D / 1B 比较合适。
参考代码
1 |
|
E
题目描述
给定一张 $n$ 个点，$m$ 条边的无向图。每条边标有 D 或 d。
定义无序点对 $(x, y)$ 是「铁的」，当且仅当 $x \neq y$ 且 $x, y$ 之间存在同时出现 D 和 d 的简单路径。
小 A 深知自由组合定律 DdTt 的重要性，所以他让你对这样的点对计数。
注意：
- 简单路径定义为不经过重复 节点 的路径。
- 保证图无自环，连通，可能有重边。
数据范围
- Subtask #1（6 points）：$n \leq 8$，$m \leq 21$。
- Subtask #2（16 points）：$n\leq 15$，$m\leq 822$。依赖 Subtask #1。
- Subtask #3（17 points）：$m = n - 1$。
- Subtask #4（18 points）：$m = n$。
- Subtask #5（19 points）：$n\leq 1064$，$m\leq 10 ^ 4$。依赖 Subtask #2。
- Subtask #6（24 points）：无特殊限制。依赖 Subtask #3，#4，#5。
对于 $100%$ 的数据：
- $2\leq n \leq 4\times 10 ^ 5$，$n - 1\leq m\leq 10 ^ 6$。
- $1\leq x, y\leq n$。
- $c\in {\texttt{D}, \texttt{d}}$。
- 保证图无自环，连通，可能有重边。
Sol
补集转化变成不存在同时出现 D（1）和 d（0）的简单路径。
如果点对之间不存在出现 $01$ 的路径，只有以下三种情况：
- 只有 $0$ 路径。
- 只有 $1$ 路径。
- 同时有 $0$ 路径和 $1$ 路径。
接下来的推导需多次应用如下基本事实：
性质 1：对于点数 $\geq 3$ 的点双，任给两点 $x\neq y$，存在经过 $x, y$ 的简单环。
点双基本性质。若 $x, y$ 不直接相连，由 门杰定理 $k = 2$ 的特殊情形可证。若 $x, y$ 直接相连，若删去 $(x, y)$ 后 $x, y$ 不连通，不妨设 $x$ 所在连通块大小 $\geq 2$，则 $x$ 为原图割点，矛盾，因此删去 $(x, y)$ 后 $x, y$ 连通，从而得到经过 $x, y$ 的简单环。证毕。
Part 1
对于只有 $0$ 路径的情况，考虑点双 $B$，容易猜测若存在 $1$ 边则经过 $B$ 的点对不合法。
性质 2：对于点数 $\geq 3$ 的点双，任给一点 $x$ 与一边 $e$，存在经过 $x, e$ 的简单环。
证明：将 $e = (u, v)$ 拆成 $(u, w)$ 和 $(w, v)$ 不影响 $B$ 点双连通性。据性质 1，存在经过 $x, w$ 的简单环。因 $w$ 仅与 $u, v$ 相连，故 $(u, w), (w, v)$ 在环上，将其替换为 $(u, v)$ 可得经过 $x, e$ 的简单环。证毕。
- 不影响点双连通性的证明：删去 $u$ 或 $v$，因 $w$ 与 $v$ 或 $u$ 连通且 $B$ 删去 $u$ 或 $v$ 后连通可知 $u, v$ 不是割点；删去 $u, v, w$ 以外的点时，将 $(u, w)$ 和 $(w, v)$ 视为 $(u, v)$，$B$ 连通；删去 $w$ 相当于删去 $(u, v)$，若图不连通则 $(u, v)$ 在 $B$ 上为割边，当点数 $\geq 3$ 时 $u$ 或 $v$ 在 $B$ 上为割点，矛盾，故 $B$ 连通。
性质 3：对于点数 $\geq 3$ 的点双，点双内任给两点 $x\neq y$ 与一边 $e$，存在 $x \to e \to y$ 的简单路径。
证明：由性质 2，存在经过 $x, e$ 的简单环 $C$，若 $y\in C$ 显然成立，否则令 $P$ 为任意 $y\to x$ 路径，考虑 $P$ 与 $C$ 的第一个交点 $z$，存在使得 $z \neq x$ 的 $P$，否则 $x$ 为割点：删去 $x$ 后 $y$ 无法到达 $C$ 剩余节点。令 $Q = y \to z$ 接上 $z$ 通过环上有 $e$ 的一侧到 $x$ 的路径，则 $Q$ 为 $x \to e\to y$ 的简单路径。证毕。
令 $e$ 为 $1$ 边，对点双内任意两点 $x\neq y$ 应用性质 3，结合 $|B| = 2$ 的平凡情况，可得
结论 1：若点双内存在 $1$ 边，则经过该点双的点对不合法。
因此，删去有 $1$ 边的点双内部所有边，剩余连通块大小选 $2$ 之和即为所求。
对于只有 $1$ 路径的情况同理。
Part 2
同时有 $0$ 路径和 $1$ 路径的点对是本题重点，下称「合法点对」。
结论 2：若两点之间存在割点，则不合法。
证明：设 $x, y$ 间存在割点 $z$。考虑 $x\to z$ 和 $z\to y$ 的所有路径，它们仅在 $z$ 处相交，否则与 $z$ 为割点矛盾。若同时存在 $0$ 路径 $P_0$ 和 $1$ 路径 $P_1$，将 $P_0$ 在 $x\to z$ 的部分和 $P_1$ 在 $z\to y$ 的部分相接得到 $01$ 路径，不合法。证毕。
可以推出合法点对属于相同点双，考虑点双 $B = (V, E)$，感性猜测 $B$ 内部最多有一对合法对，接下来证明这一点。
考虑合法点对 $x, y$。令 $x\to y$ 所有 $0$ 路径覆盖点集 $V_0$，所有 $1$ 路径覆盖点集 $V_1$。
结论 3.1：除 $x, y$ 以外，$V_0$ 与 $V_1$ 无交。
证明：若有交，则可通过 $P_0$ 与 $P_1$ 第一个交点调整得到 $01$ 路径。证毕。
结论 3.2：$V_0$ 与 $V_1$ 之间无边。
证明：若有边 $u\to v$ 满足 $u\in V_0, v\in V_1$，则 $x\to u \to v \to y$ 为 $01$ 路径。证毕。
性质 4：对于点数 $\geq 3$ 的点双，任给不同三点 $x, y, z$，存在经过 $x, y, z$ 且以 $x, y$ 为端点的简单路径。
证明：由性质 1，存在经过 $x, z$ 的简单环 $C$，若 $y\in C$ 显然成立，否则令 $P$ 为任意 $y\to x$ 路径，考虑 $P$ 与 $C$ 的第一个交点 $u$，存在使得 $u \neq x$ 的 $P$，否则 $x$ 为割点：删去 $x$ 后 $y$ 无法到达 $C$ 剩余节点。令 $Q = y \to u$ 接上 $u$ 通过环上有 $z$ 的一侧到 $x$ 的路径，则 $Q$ 为经过 $x, y, z$ 且以 $x, y$ 为端点的简单路径。 证毕。
结论 3.3：$V_0 \cup V_1 = V$。
证明：对任意 $z\neq x, y$ 应用性质 4，证毕。
考虑 $z\in V_0$，$z’\in V_0$ 且 $(x, y) \neq (z, z’)$。
结论 4：存在 $x, y$ 分别到 $z, z’$ 或 $z’, z$ 的两条仅经过 $V_0$ 的不交路径。
证明：若 $z$ 或 $z’$ 与 $x$ 或 $y$ 相等，显然。否则考虑仅经过 $V_0$ 的 $x\to z \to y$ 的任意 有序 路径 $P$，$x\to z’ \to y$ 的任意 有序 路径 $P’$，令它们的交点为 $Q$。若 $z\in Q$ 或 $z’\in Q$，可得同时经过 $x, y, z, z’$ 的路径且 $x, y$ 分别在两端，显然。否则将 $Q$ 按照在 $P$ 中的出现顺序标号 $q_1, q_2, \cdots, q_k$，注意 $x, y\in Q$。令 $z’$ 两侧与 $z’$ 距离最近的两个交点分别为 $q_i$ 与 $q_j$，则令
$$
P’’ = x\xrightarrow{P} q_{\min(i, j)} \xrightarrow{P’} z’ \xrightarrow{P’} q_{\max(i, j)} \xrightarrow{P} y
$$
这样，$P$ 与 $P’’$ 的所有交点按顺序出现，即令 $P$ 与 $P’’$ 的交点为 $Q’$，将 $Q’$ 按照在 $P$ 中的出现顺序标号为 $q_1’, q_2’, \cdots, q_k’$，则 $P’’$ 上 $Q’$ 出现顺序也为 $q_1’, q_2’, \cdots, q_k’$。设 $z$ 两侧与 $z$ 距离最近的两个交点分别为 $q_c$ 与 $q_{c + 1}$，$z’$ 为 $q_d$ 与 $q_{d + 1}$。当 $c\leq d$ 时，令 $P_z = x\xrightarrow {P} q_c \xrightarrow{P} z$，$P_{z’} = z’\xrightarrow{P’} q_{d + 1} \xrightarrow{P’} y$，合法。当 $c > d$ 时只需反过来构造即可。证毕。
因此，对于任意 $z, z’ \in V_0 \land (x, y) \neq (z, z’) \land z\neq z’$，存在 $x, y$ 分别到 $z, z’$ 或 $z’, z$ 的两条仅经过 $V_0$ 的不交路径。将这两条路径通过 $x, y$ 之间的全 $1$ 路径连起来，得 $z, z’$ 之间不合法。
同理，对于任意 $z, z’ \in V_1 \land (x, y) \neq (z, z’) \land z\neq z’$，$z, z’$ 之间不合法。
而 $z\in V_0$，$z’\in V_1$ 且 $(x, y) \neq (z, z’)$ 之间显然不合法。
综上，$S$ 内部最多有一对合法对。
考虑充要条件，其等价于点双内恰好存在两个点满足同时有 $01$ 出边。
充分性：考虑令唯二的两个点分别为 $x, y$。根据性质 4，考虑任意 $x\to u\to y$，路径必然纯色，否则考虑切换颜色的点，该点同时存在 $01$ 出边。因 $x, y$ 同时有 $0, 1$ 出边，故存在全 $0$ 路径和全 $1$ 路径。
必要性：当 $x, y$ 合法时，根据结论 3.2 可知仅有 $x, y$ 同时有 $01$ 出边。
问题在 $\mathcal{O}(n + m)$ 的时间内解决。
参考代码
1 |
|
F
题目描述
如果小 A 是一个，一个一个一个毒瘤，他会让你求解套了十层甚至九层娃的幂塔方程，但他不是。
他想让你求解：
$$
x ^ x\equiv D \pmod n
$$
保证 $n$ 的最大质因子不超过 $10 ^ 5$，且 $D$ 与 $n$ 互质。
你需要保证得到的解 $x$ 为 $[0, 2 ^ {125}]$ 范围内的整数。若该范围内无解，输出 $-1$；若存在多解，输出任意一个。
多组测试数据。
数据范围
- Subtask #1（5 points）：$n\leq 20$。
- Subtask #2（8 points）：$n\leq 400$。依赖 Subtask #1。
- Subtask #3（11 points）：$n$ 是质数，$T\leq 10 ^ 4$。
- Subtask #4（15 points）：$\mu(n) \neq 0$，$T\leq 100$。
- Subtask #5（9 points）：$\mu(n) \neq 0$，$T\leq 10 ^ 4$。依赖 Subtask #4。
- Subtask #6（13 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 100$。
- Subtask #7（7 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 10 ^ 4$。依赖 Subtask #3，#6。
- Subtask #8（6 points）：$m\leq 1064$。依赖 Subtask #2。
- Subtask #9（16 points）：$n\leq 10 ^ 9$，$T\leq 10 ^ 4$。
- Subtask #10（10 points）：无特殊限制。依赖 Subtask #5，#7，#8，#9。
对于 $100%$ 的数据：
- $1\leq T\leq 4\times 10 ^ 4$。
- $2\leq n \leq 10 ^ {18}$。
- $1\leq D < n$，$D\perp n$。
- $2\leq p_1 < p_2 < \cdots < p_k \leq 10 ^ 5$。
Sol 0
验题人 chenxia25 给出了一个假做法：将 $n$ 分解质因数，对于每个 $p ^ k$ 可以单独求解。然后 excrt 合并。
问题在于 $p ^ k$ 很大，且 $p ^ k \times \varphi(p ^ k)$ 可能不互质，但对于单独求解的 $p ^ k$ 得到的解互质（因为有多解），导致同余方程合并时无解。
Sol 1
考虑 $n = p$。
令 $x_1$ 为 $x \equiv D \pmod p$ 和 $x \equiv 1 \pmod {p - 1}$ 的解，容易发现 $x_1$ 存在。
Sol 2
考虑 $n = p ^ k$。
考虑 增量法构造。
设 $x_i ^ {x_i} \equiv D \pmod {p ^ i}$。考虑如何 $x_i$ 推到 $x_{i + 1}$。
容易发现令 $x_i \gets x_i + Ip ^ i(p - 1)$ 仍然可行，因此设 $x_{i + 1} = x_i + Ip ^ i(p - 1)$。
考虑求出 $I$。因为 $x_{i + 1} ^ {x _{i + 1}} \equiv D \pmod {p ^ {i + 1}}$，所以 $(x_i + Ip ^ i(p - 1)) ^ {x_i + Ip ^ i(p - 1)} \equiv D \pmod {p ^ {i + 1}}$。
因为 $D$ 和 $p ^ i$ 互质，所以 $x_i$ 必然和 $p ^ i$ 互质，所以 $x_i + Ip ^ i(p - 1)$ 和 $p ^ i$ 互质，故和 $p ^ {i + 1}$ 互质。欧拉定理可以用。
因为 $\varphi(p ^ {i + 1}) = p ^ i(p - 1)$，所以 $Ip ^ i(p - 1)\equiv 0\pmod {\varphi(p ^ {i + 1})}$，因此 $(x_i + Ip ^ i(p - 1)) ^ {x_i} \equiv D \pmod {p ^ {i + 1}}$。
这是一个 n 次剩余的形式。但是 $p ^ {i + 1}$ 太大，无法使用 BSGS 求解。
注意到 $Ip ^ i(p - 1)$ 的大于 $1$ 次方 $\bmod\ p ^ {i + 1}$ 等于 $0$，考虑 二项式展开。
$$
(x_i + Ip ^ i(p - 1)) ^ {x_i} \equiv x_i ^ {x_i} + \dbinom{x_i} 1 x_i ^ {x_i - 1} \cdot Ip ^ i(p - 1) \equiv D \pmod {p ^ {i + 1}}
$$
令 $v = x_i ^ {x_i}$，则 $vIp ^ i(p - 1)\equiv D - v\pmod {p ^ {i + 1}}$，即 $I\equiv \dfrac{D - v}{v p ^ i (p - 1)} \pmod {p ^ {i + 1}}$。
因为 $v \equiv D \pmod {p ^ i}$，所以 $D - v$ 是 $p ^ i$ 的倍数。设 $t = \dfrac {D - v}{p ^ i}$，则 $I \equiv \dfrac t {v(p - 1)} \pmod p$，显然 $v(p - 1) \perp p$，因此 $v(p - 1)$ 在模 $p$ 意义下的逆元存在，据此可求出 $I$。
注意到 $I < p$，因此 $I p ^ i (p - 1) < p ^ {i + 1}(p - 1)$，构造出的解远小于 $2 ^ {125}$ 这一上界，算法可行。
时间复杂度约为 $\mathcal{O}(T\log m\log n)$。
Sol 3
考虑 $n$ 是 square free number。
考虑 增量法构造。
设 $n$ 的质因子分别为 $p_1, p_2, \cdots, p_k$，令 $P_i = \prod\limits_{j = 1} ^ i p_j$，$Q_i = \prod\limits_{j = 1} ^ i (p_j - 1) $。
设 $x_i \equiv D \pmod {P_i}$，考虑如何从 $x_i$ 推到 $x_{i + 1}$。
如法炮制，发现令 $x_i \gets x_i + IP_iQ_i$ 仍然可行，因此设 $x_{i + 1} = x_i + IP_iQ_i$。但是再走二项式展开的老路就行不通了，因为 $P_iQ_i \not \equiv 0 \pmod {\varphi(P_{i + 1})}$。
怎么办呢？注意到若需保证 $x_{i + 1} ^ {x_{i + 1}} \equiv D \pmod {P_{i + 1}}$，因为必然有 $(x_i + IP_iQ_i) ^ {x_i + IP_iQ_i} \equiv D\pmod {P_i}$ 且 $P_i \perp p_{i + 1}$，根据中国剩余定理，只需保证 $(x_i + IP_iQ_i) ^ {x_i + IP_iQ_i} \equiv D\pmod {p_{i + 1}}$。发现还是很不好做，因为 $I$ 同时在底数和指数上，而且 $P_iQ_i \not \equiv 0 \pmod {p_{i + 1} - 1}$。
考虑化去指数上的 $I$。
尝试改变定义，令 $x_{i + 1} = x_i + IP_iQ_{i + 1}$，因为 $Q_{i + 1} \perp p_{i + 1}$，这为接下来寻找逆元奠定基础（如果令 $x_{i + 1} = x_i + IP_{i + 1}Q_{i + 1}$，实际上相当于给 $x_i$ 加上 $x_{i + 1}$ 的循环节 $\mathrm{lcm}(P_i, \varphi(P_i))$ 的倍数 $P_{i + 1}Q_{i + 1}$ 的倍数，显然不可行，因为当且仅当 $x_i$ 已经符合要求时我们能找到合法的 $x_{i + 1}$）且 $Q_{i + 1} \equiv 0 \pmod {p_{i + 1} - 1}$。
这样一来，上式化简为 $(x_i + IP_iQ_{i + 1}) ^ {x_i} \equiv D\pmod {p_{i + 1}}$。求解该 n 次剩余，令 $g$ 为 $p_{i + 1}$ 的任意原根，$g ^ u \equiv D\pmod {p_{i + 1}}$，则 $I \equiv \dfrac {g ^ {\frac u {x_i}} - x_i}{P_i Q_{i + 1}} \pmod {p_{i + 1}}$。
此时出现了一个严重的问题。分子的 $\dfrac u {x_i}$ 在模 $p_{i +1} - 1$ 意义下求解，但 $x_i$ 和 $p_{i + 1} - 1$ 可能不互质。
尝试修补这个问题。即尝试令 $x_i \perp p_{i + 1} - 1$。
接下来是一步巧妙转化：令 $x’i \gets x_i + JP_iQ_i$，使得 $x_i + JP_iQ_i \perp p{i + 1} - 1$。
但是又出现了问题，即 $P_iQ_i$ 可能和 $p_{i + 1} - 1$ 不互质。
给出引理：若 $a\perp d$，则对于任意 $n\geq 2$，存在 $J\in [0, n - 1]$ 使得 $a + Jd \perp n$。
证明：将 $n$ 分解质因数成 $\prod q_i ^ {c_i}$ 的形式。容易证明 $a \perp q_i ^ {c_i}$ 或 $a + d \perp q_i ^ {c_i}$。若非，说明 $a$ 和 $d$ 同时含有质因子 $q_i$，与假设矛盾。又因为若 $a + Jd \perp q_i ^ {c_i}$，显然 $a + (J + kq_i ^ {c_i})d \perp q_i ^ {c_i}$，即 $J$ 在 $q_i ^ {c_i}$ 模意义下。根据中国剩余定理，得证。
我们发现这是一个递归形式的问题，即若 归纳假设 $x_i \perp P_iQ_i$，则能找到这样的 $J$ 使得 $x_i + JP_iQ_i \perp p_{i + 1} - 1$，且上述引理给出了一个求解 $J$ 的方法，即对 $p_i - 1$ 分解质因数并 CRT 合并。而 若条件满足，则结论满足，推出下一轮的条件仍满足：$x’i \perp p{i + 1} - 1 \Rightarrow x’i \perp P_iQ{i + 1} \Rightarrow x’i + IP_iQ{i + 1} \perp P_iQ_{i + 1} \Rightarrow x_{i + 1}\perp P_iQ_{i + 1}$，又因为 $D\perp P_{i + 1}$，所以 $x_{i + 1} \perp P_{i + 1}Q_{i + 1}$。
同时，当在构造第一步时，Sol 2 满足归纳的初始条件，因为 $x_1 \equiv D \pmod {p_i}$ 且 $x_1 \equiv 1 \pmod {p_1 - 1}$，显然 $x_1\perp P_1Q_1$。
梳理一下上面的思路，发现添加限制 $x_i \perp P_iQ_i$ 之后，为了满足该性质所需进行的操作的正确性被该性质所保证，而一开始性质满足，故正确性得以保证。这是归纳法非常巧妙的应用。
这样，我们解决了 $\dfrac u {x_i}$ 可能无解的问题。
$P_iQ_{i + 1}$ 与 $p_{i + 1}$ 互质，其在模 $p_{i + 1}$ 意义下存在逆元。我们得以算出 $I \equiv \dfrac {g ^ {\frac u {x’i}} - x’i}{P_i Q{i + 1}} \pmod {p{i + 1}}$，从 $x_i$ 扩展至 $x_{i + 1}$。
时间复杂度约为 $\mathcal{O}(m ^ {\frac 5 4} + T\omega(n)(\log n + \sqrt m))$：预处理 $m$ 以内每个质数（约 $\frac m {\ln m}$ 个）的原根（单次复杂度 $m ^ {\frac 1 4} \log m$）。BSGS 求解离散对数方程时模数非常小，不需要 map 或哈希表，用数组记录即可。
由于 $I, J$ 均为 $p_{i + 1}$ 级别，因此对应的 $\sum IP_iQ_{i + 1}$ 和 $\sum JP_iQ_i$ 的一个粗略上界为 $\omega(n) n ^ 2$，略小于 $2 ^ {125}$ 的限制，符合要求。若担心超出上界，可以令 $x_i$ 对 $P_iQ_i$ 取模。
Sol 4
结合 Sol 2 和 Sol 3，从小到大考虑所有质因子。若相邻两个质因子相同，则使用 Sol 2，将对应的 $p ^ i (p - 1)$ 换成 $P_iQ_i$；否则使用 Sol 3 即可。
接下来是一些细节讨论：
- 在 Sol 2 使用欧拉定理时，需要 $IP_iQ_i \equiv 0 \pmod {\varphi(P_{i + 1})}$。考虑 $P_iQ_i$ 包含 $k$ 个质因子 $p_i$，则 $\varphi(P_{i + 1})$ 也包含 $k$ 个质因子（根据欧拉定理的计算式可得）。同时，$\varphi(P_{i + 1})$ 所有形如 $p_j - 1$ 的乘积项被 $Q_i$ 消去，因此上式仍然成立。
- 在 Sol 2 二项式展开时，需要 $IP_iQ_i$ 的大于 $1$ 次幂是 $P_{i + 1}$ 的倍数。显然成立，因为 $p_i = p_{i + 1}$。
- 在 Sol 2 求解 $I$ 时，需要 $\dfrac {D - v}{vP_iQ_i}$ 在模 $P_{i + 1}$ 意义下存在。由于分子，分母和模数均为 $P_i$ 的倍数，因此同除后分母 $vQ_i$ 和 $p_{i + 1}$ 互质，这是因为 $v$ 显然和 $p_i$ 互质，且 $p_{i + 1} = p_i$。
- 在 Sol 3 中的归纳假设需要在 Sol 2 中满足，因为我们会交替使用 Sol 2 和 Sol 3。因为 Sol 2 的初始条件成立，所以 $x_i \perp P_iQ_i$。因为 $P_{i + 1}Q_{i + 1}$ 相较于 $P_iQ_i$ 没有增加更多质因子，所以显然 $x_{i + 1}\perp P_{i + 1}Q_{i + 1}$。
综上，时间复杂度 $\mathcal{O}(m ^ {\frac 5 4} + T((\omega(n) + \log m)\log n + \omega(n) \sqrt m))$，常数较大。
可以获得 100 分的好成绩。
接下来是一些补充：
- 在求解 $J$ 时，可以每次给 $x_i$ 加上 $P_iQ_i$ 直到符合要求而非 CRT 求解。因为每次加上 $P_iQ_i$ 可以看做从 $0\sim p_{i + 1} - 1$ 中随机选一个数，期望随机 $\dfrac {p_{i + 1} - 1} {\varphi(p_{i + 1} - 1)} - 1$ 次（初始状态算一次）即可得到与 $p_{i + 1} - 1$ 互质的 $x_i + JP_iQ_i$。
- 笔者认为本题是一道不可多得的数论好题。尽管其形式简单，但却涉及到了 exgcd 求逆元，CRT 合并同余方程，BSGS 求解离散对数和 n 次剩余问题。归纳法用得恰到好处。整个算法优美而简洁，思维难度极高。没有冗余步骤，只是纯粹的数论。
参考代码
1 |
|