题解：P6962 [NEERC 2017] Knapsack Cryptosystem

超绝值域分治。

考虑 $n\le 42$ 时，我们可以暴力 meet-in-the-middle，把 $n$ 个数分成个数尽量相等的两堆，每堆里枚举子集，把该子集中数的和记录在一个哈希表中。然后枚举第一堆的哈希表里的值 $x$，查询第二堆的哈希表中是否存在 $s-x$。若存在则输出。复杂度 $O(2^{\frac{n}{2}})$（使用 unordered_map，近似 $O(1)$）。

若 $n>42$，则根据题面中给定的 $\{a\}$ 的生成方式，不难得出结论：$a_1\le 2^{64-n}\le 2^{64-43}=2^{21}$。那么我们枚举真正的 $a_1$ 的复杂度是可以接受的。枚举 $a_1$ 后就能得到一系列可能的 $r$ 使得 $a_1\times r \equiv b_1 \pmod {2^{64}}$。因为保证 $r$ 和 $2^{64}$ 互质，意味着 $r$ 存在逆元，确定 $r$ 后就能还原出整个 $\{a\}$。此时判定一下还原后的序列是否合法即可。若合法且存在解就输出（由于 $a$ 的某一项必然大于前面的项的和，易证若有解必为唯一解，构造方式是从大往小贪心，如果能减就减）。

现在的问题在于求出一个 $a_1$ 对应的 $r$（们）。我们有式子：

设 $b_1=2^k\times p$，其中 $p$ 是奇数，那么此式等价于：

这个式子告诉我们， $2^k\mid a_1$。因此合法的 $a_1=x\times2^k,x\in[1,2^{64-n-k}]$，只有 $2^{64-n-k}$ 种。

由于我们想要从 $\{b\}$ 还原出 $\{a\}$，所以其实我们只关心 $r$ 的逆元 $r^{-1}$ 的值。将上式变形：

$\dfrac{a_1}{2^k}\equiv p \times r^{-1}\pmod {2^{64-k}}$ $r^{-1}\equiv \dfrac{a_1}{2^k} \times p^{-1}\pmod {2^{64-k}}$

其中，$p$ 由 $b_1$ 确定，即是一个确切值；同时 $p$ 一定是奇数，因此 $p^{-1}$ 一定存在且固定。

因此只要确定了 $a_1$，就确定了 $r^{-1} \bmod {2^{64-k}}=\dfrac{a_1}{2^k} \times p^{-1}$。也即，$r^{-1}=y\times 2^{64-k}+\dfrac{a_1}{2^k} \times p^{-1}, y\in [0,2^{k})$。

因此对于一个 $a_1$，合法的 $r$ 的数量是 $2^k$ 种。整体上合法的 $(a_1,r)$ 数对就只有 $2^{64-n-k}\times 2^k=2^{64-n}$ 种情况。每种情况在得到 $r^{-1}$ 后的判定是 $O(n)$ 的，因此总复杂度为 $O(n\times2^{64-n})$。

在 $42<n\le 64$ 时，这个值在 $n=43$ 时取极大值 $43\times 2^{21}=90177536$，是 $9\times 10^7$ 的量级，常数较小的实现方式可以轻松通过。