P12239 [蓝桥杯 2023 国 Java A] 游戏的得分 题解

· · 题解

下记 p=998244353。

首先考虑一个简化版本的问题：

小 A 和小 B 玩若干轮游戏，每轮获胜者加 2 分，失败者加 1 分，已知 a,b 是两人分数模 k 的余数，求游戏最小轮数。

即：有 2 个非负整数 A,B，满足 \frac{\max\{A,B\}}{\min\{A,B\}}\le2 且 3|A+B，已知它们模 k 的余数 a,b，求 \frac{A+B}3 的最小值。

跑一下 BSGS 可以得到 k（即 2 模 p 的阶）是 \frac{p-1}2=499122176，这个数并不是 3 的倍数，所以通过将 a,b 增加同等数量的 k 可以达到条件，而且所需的数量不大。直接贪心：每次取 a,b 中较小的一个增加 k，直到满足条件。这个子问题的时间复杂度是 O(1)，可能相对某些数学做法更慢，但是足够通过本题。

那么我们接下来就只需要解决以下这个问题：

这不就是一个 BSGS 裸题吗？等等：BSGS 是 O(\sqrt p) 的，这样总复杂度就是 10^9 量级的，显然不能通过。

我们仔细研究一下 BSGS 的实现（假设你已经学过了 BSGS），然后考虑优化。

定义一个常数 k=\lceil\sqrt p\rceil。然后先预处理 ba^B 的所有取值（0\le B<k），用数据结构存储，再枚举 a^{Ak} 的值（1\le A\le k 或 1\le A\le\lceil\frac pk\rceil），找到 a^{Ak}\equiv ba^B\pmod p，则有 a^{Ak-B}\equiv b\pmod p。（参考 OI Wiki 上的实现）

> 定义一个常数 $k$。然后先预处理 $a^{Ak}$ 的所有取值（$1\le A\le\lceil\frac p{2k}\rceil$），用数据结构存储，再枚举 $ba^B$ 的值（$0\le B<k$），找到 $a^{Ak}\equiv ba^B\pmod p$，则有 $a^{Ak-B}\equiv b\pmod p$。 总时间复杂度为 $O(\frac p{2k}+mk)$。取 $k=\lceil\sqrt\frac p{2m}\rceil=50$，则时间复杂度为 $O(\sqrt{pm})$，量级为 $10^7$，可以通过本题。 注：这里假设哈希表的单次操作复杂度为 $O(1)$，因为一些显然的原因，需要手写哈希表。$a^{Ak}$ 分布较为均匀且与输入数据无关（不会被卡），所以直接取模即可，单个链表内不会超过 $10$ 个数据。注意 BSGS 算法无法解决答案为 $0$ 的情况，需要特判。 [提交记录](https://www.luogu.com.cn/record/215849807)