题解：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（们）。我们有式子：

a_1\times r \equiv b_1 \pmod {2^{64}}

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

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

这个式子告诉我们， 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 的量级，常数较小的实现方式可以轻松通过。