P6962 [NEERC 2017] Knapsack Cryptosystem

Merkle-Hellman 背包密码系统是由 Ralph Merkle 和 Martin Hellman 于 1978 年发明的最早的公钥密码系统之一。以下是其描述： Alice 选择 $n$ 个正整数 ${a_{1}, . . . , a_{n}}$，使得每个 $a_{i} > \sum^{i-1}_{j=1}a_{j}$，一个大于所有 $a_{i}$ 之和的正整数 $q$，以及一个与 $q$ 互质的正整数 $r$。这 $n + 2$ 个整数是 Alice 的私钥。 然后 Alice 计算 $b_i = (a_{i} \cdot r)$ mod $q$。这 $n$ 个整数是 Alice 的公钥。 知道她的公钥后，Bob 可以向 Alice 传输一个 $n$ 位的消息。为此，他计算 $s$，即在消息中第 $i$ 位为 1 的位置上对应的 $b_{i}$ 的和。这个值 $s$ 是加密后的消息。 注意，窃听者 Eve 知道加密消息和公钥，必须解决一个（可能很难的）背包问题实例才能找到原始消息。同时，在收到 $s$ 后，Alice 可以在线性时间内计算出原始消息；我们将其留给你作为练习。 在这个问题中，你需要处理 Merkle-Hellman 背包密码系统的实现，其中 Alice 选择了 $q = 2^{64}$，出于显而易见的性能原因，并公布了此信息。由于每个人都知道她的 $q$，她要求 Bob 发送给她取模 $2^{64}$ 的计算值 $s$ 以简化通信。 你需要破解这个实现。给定公钥和一个加密消息，恢复原始消息。

第一行包含一个整数 $n (1 \le n \le 64)$。 接下来的 $n$ 行中，每行包含一个整数 $b_{i} (1 \le b_{i} < 2^{64})$。 最后一行包含一个整数 $s$ mod $q$ —— 取模 $q$ 的加密消息 $s$，其中 $0 \le s$ mod $q < 2^{64}$。 给定的序列 $b_{i}$ 是描述的实现中的有效公钥，给定的值 $s$ mod $q$ 是有效的加密消息。

输出恰好 $n$ 位（$0$ 或 $1$ 数字）——原始消息。

时间限制：3 秒，内存限制：512 MB。 题面翻译由 ChatGPT-4o 提供。