P8305 题解

· · 题解

题目大意

给出一个 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\}$ 较小时，若每次随机的 $seed$ 得到的 hash 存在于 `unordered_map`，则较大概率这个种子合法。可以简单地认为检查一个种子是否合法是 $O(1)$ 的。相当于每次检查 $2^{32}$ 个种子中的一个是否在 $O(n)$ 个种子中，每次成功率约 $n/2^{32}$。 --- 我们可以数据分治，在 $\max\{a\} \ge 1000$ 时使用做法 $\bf 1$，否则使用做法 $\bf 2$。调参后即可 AC。