[CoE R4 E] 伪随机

Luogu

IDLGP8305

Time1000ms

Memory256MB

DifficultyP6

洛谷原创Special JudgeO2优化洛谷月赛

很久很久以前，小明生成了一些数据。他的数据生成器使用了以下两个函数生成随机数： ```plain 定义函数 srand(32 位无符号整数 seed) 将 x 赋值为 seed 定义函数 rand() 将 x 赋值为 x 异或 (x 左移 13 位) 将 x 赋值为 x 异或 (x 右移 17 位) 将 x 赋值为 x 异或 (x 左移 5 位) 返回 x ``` 小明在调用 $\text{srand(seed)}$ 后，连续调用了 $n$ 次 $\text{rand()}$，并且记录下了每次 $\text{rand()}$ 的返回值对 $p$ 取模时得到的余数 $a_i$。很久很久以后，只有数据生成器依然残存（实现见下发文件的 `generator.cpp`），但生成器的参数 $\text{seed}$ 和 $p$ 已经消失。小明想要从数据中恢复这两个参数。即给定序列 $a_i$，需要找到任意一组 $\text{seed}$ 和 $p$ 的可能的值。你能帮帮他吗？ --- **简要描述** 小明的数据生成器是下发文件的 `generator.cpp`。你需要根据生成器的输出，反推出生成器的输入。 ## Input 输入的第一行包含一个整数 $n$。第二行包含 $n$ 个 $32$ 位无符号整数 $a_1, a_2, \cdots, a_n$，为小明生成的数据。 ## Output 输出仅包含两个 $32$ 位无符号整数 $\text{seed}$ 和 $p$，为你的答案。你需要保证 $0 < \text{seed}, p < 2^{32}$。如果有多组解，你可以输出任意一组。 [samples] ## Note ### 数据规模本题共有 $50$ 个测试点，每个测试点 $2$ 分。对于所有数据，保证 $n = 10^5$，$\text{seed}$ 是随机选取的，且至少存在一组解。

Samples

Input #1

见下发文件的 sample.in

Output #1

见下发文件的 sample.out

API Response (JSON)

{
  "problem": {
    "name": "[CoE R4 E] 伪随机",
    "description": {
      "content": "很久很久以前，小明生成了一些数据。 他的数据生成器使用了以下两个函数生成随机数： ```plain 定义函数 srand(32 位无符号整数 seed) \t将 x 赋值为 seed 定义函数 rand() \t将 x 赋值为 x 异或 (x 左移 13 位) \t将 x 赋值为 x 异或 (x 右移 17 位) \t将 x 赋值为 x 异或 (x 左移 5 位) \t返回 x ``` 小明在调用 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8305"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "很久很久以前，小明生成了一些数据。\n\n他的数据生成器使用了以下两个函数生成随机数：\n\n```plain\n定义函数 srand(32 位无符号整数 seed)\n\t将 x 赋值为 seed\n\n定义函数 rand()\n\t将 x 赋值为 x 异或 (x 左移 13 位)\n\t将 x 赋值为 x 异或 (x 右移 17 位)\n\t将 x 赋值为 x 异或 (x 左移 5 位)\n\t返回 x\n```\n\n小明在调用 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments