自动搬运

查看原文

来自洛谷，原作者为

	yzy1 Меня мое сердце, в тревожную даль зовёт.

搬运于2025-08-24 22:37:51，当前版本为作者最后更新于2022-04-28 09:29:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意

给出一个 XOR-Shift 生成的长度为 $n=10^5$ 的数列 $a$，数列元素对 $p$ 取模。根据数列还原 XOR-Shift 的种子 $seed$ 和 $p$。

算法 $\bf 1$

显然 $p$ 大于 $a$ 中最大值。易得 $p$ 应在 $\max\{a\} + \max\{a\}/n$ 附近。设 $b$ 为取模前的 $a$ 数列。特别地，$b_0=seed$。考虑如何从 $b_i$ 得到 $b_{i-1}$：把 $b_{i-1}$ 的每个二进制位设为未知数，由 XOR-Shift 的过程列出异或方程组，高斯消元解出。假设 $p$ 已经固定，则 $b_1 \in \{kp+a_1 \mid k \in \mathbb N\}$。又由于取值范围 $32$ 位无符号整数。故 $b_1$ 只有 $O(V / p)$ 种取值。由此我们可以得到一个基于随机化的算法：每次从 $\max\{a\}+1$ 到 $\max\{a\} + 3\max\{a\}/n+1$ 随机一个整数作为 $p$，然后从所有可能成为 $b_1$ 的整数中随机一个作为 $b_1$，检查是否合法。若合法则通过高斯消元得到 $b_0$。

设答案唯一，则每次尝试得到答案的概率约为：

$$\frac{1}{(\frac{3\max\{a\}}{n}+1) \frac{2^{32}}{\max\{a\}}} $$

当 $\max\{a\}$ 较大时，概率约等于 $\dfrac n {3\times 2^{32}}$，该算法表现较好。但 $\max\{a\}$ 较小时不佳。调整参数后该算法可获得 $80$ 分。

算法 $\bf 2$

$\max\{a\}$ 较小时，可认为 $p=\max\{a\}+1$。考虑用类似 P7350 这题的方式来做这道题。计算出 $a$ 的所有长度为 $50$ 的子区间的 hash 值存入 unordered_map。每次随机一个 $seed$，生成一个长度为 $50$ 的序列，查 unordered_map 判断这个序列是否和 $a$ 的子区间匹配，若匹配则重复高斯消元直到还原出 $seed$，判断 $seed$ 是否合法。

这个做法正确性不太会证，仅感性理解：$\max\{a\}$ 较小时，若每次随机的 $seed$ 得到的 hash 存在于 unordered_map，则较大概率这个种子合法。可以简单地认为检查一个种子是否合法是 $O(1)$ 的。相当于每次检查 $2^{32}$ 个种子中的一个是否在 $O(n)$ 个种子中，每次成功率约 $n/2^{32}$。

---

我们可以数据分治，在 $\max\{a\} \ge 1000$ 时使用做法 $\bf 1$，否则使用做法 $\bf 2$。调参后即可 AC。