说明

卢浮宫博物馆收藏了一幅最著名的画作：蒙娜丽莎，由列奥纳多·达·芬奇在 16 世纪绘制。

这幅画被封闭在一个坚固的玻璃室中，只有输入四个不同键盘上的四个秘密密码才能打开。博物馆馆长认为这个系统坚不可摧，而你的任务就是证明她错了。

为了帮助你，一位朋友反向工程了这个系统。当在键盘上输入一个密码（用一个正整数 $C$ 表示）时，键盘会发送伪随机数生成器生成的第 $C$ 个值到中央计算机。中央计算机只考虑从四个键盘接收到的四个伪随机值的 $N$ 个最低有效位。它计算这些值的按位异或（XOR），如果结果为 0，则打开玻璃室。伪随机数生成器的描述见问题陈述末尾。

另一位朋友找到了每个键盘使用的伪随机种子。有了所有这些信息，你认为你可以检索到解锁蒙娜丽莎的四个秘密密码。

输入格式

输入包含两行，每行由空格分隔的整数组成：

• 第一行包含整数 $N$。
• 第二行包含四个整数种子。

伪随机数生成器

伪随机数生成器在每种编程语言中描述如下。你可以期望这个伪随机数生成器没有任何偏差。

C/C++

typedef unsigned long long uint64;
uint64 state[2] = { seed, seed ^ 0x7263d9bd8409f526 };
uint64 xoshiro128plus(uint64 s[2]) {
    uint64 s0 = s[0];
    uint64 s1 = s[1];
    uint64 result = s0 + s1;
    s1 ^= s0;
    s[0] = ((s0 << 55) | (s0 >> 9)) ^ s1 ^ (s1 << 14);
    s[1] = (s1 << 36) | (s1 >> 28);
    return result;
}

伪随机序列的第 $i$ 个值是对 state 第 $i$ 次应用 xoshiro128plus 的结果。

Java

long[] state = { seed, seed ^ 0x7263d9bd8409f526L };
long xoshiro128plus(long[] s) {
    long s0 = s[0];
    long s1 = s[1];
    long result = s0 + s1;
    s1 ^= s0;
    s[0] = ((s0 << 55) | (s0 >>> 9)) ^ s1 ^ (s1 << 14);
    s[1] = (s1 << 36) | (s1 >>> 28);
    return result;
}

伪随机序列的第 $i$ 个值是对 state 第 $i$ 次应用 xoshiro128plus 的结果。

Python 2 / Python 3

state = [seed, seed ^ 0x7263d9bd8409f526]
def xoshiro128plus(s):
    s0, s1 = s
    result = (s0 + s1) % 2**64
    s1 ^= s0
    new_state = [(((s0 << 55) | (s0 >> 9)) ^ s1 ^ (s1 << 14)) % 2**64,
                 ((s1 << 36) | (s1 >> 28)) % 2**64]
    return result, new_state

以下循环从第一个值开始生成伪随机序列：

while True:
    result, state = xoshiro128plus(state)
    yield result

输出格式

输出应包含一行，内容为四个整数，即四个秘密密码，用单个空格分隔。每个密码必须小于 100,000,000。保证至少存在一个解。如果存在多个解，则所有解都将被接受。

50
3641603982383516983 445363681616962640 868196408185819179 1980241222855773941

287 17609 122886 59914

提示

数据范围

• $1 \leq N \leq 50$；
• 每个种子在 $0$ 到 $2^{64} - 1$ 之间。

翻译由 DeepSeek 完成