题面https://uoj.ac/problem/72

这个题的传统做法可见：https://vfleaking.blog.uoj.ac/blog/104

我发现了一个新的做法，并已经获得了满分：https://uoj.ac/submission/393501

可以发现这份代码的亮点是我在没有经过任何下意识的压代码长度的情况下，代码长度就是目前（2020年4月18日）所有AC提交中最短的。同时，虽然我没有使用batching加速，但是我的用时依然不算很差，通过调整参数，这份提交https://uoj.ac/submission/393500 的用时更短，但是这份代码的正确率我没法保证。

UPDATE: 加上batch之后变快了一些https://uoj.ac/submission/393507 （这是使用正确率我没法保证的参数的结果）

此外，我觉得我的做法相对传统做法也更容易理解。下面是我的做法：

考虑每个位置是否在$m$个有效信息中存在，那么你可以把这个存在性用一个长度为m的数组表示出来，这个数组可以压位表示成一个m位的二进制数。记第$i$个位置对应的这个二进制数为$s[i]$。

如果我们随机选一个集合，那么这个集合的$s$值的异或和有$2 ^ {-m}$的可能是零。如果一个集合的$s$的异或和是零，这意味着对于任何一个输入$x$，这个$x$的输出值和$x \oplus s$的输出值应该一样，当然，因为噪声所以有大约$2p(\le 0.02)$的概率这两个输出值不一样。

如果异或和不是零，那么一定有一个$x$使得它的输出值和$x \oplus s$的输出值不一样，如果不存在，那么容易发现$h$函数一定可以化简为少于$m$个输入上的函数。同样我们可以证明，随机一个$x$，它的输出值和$x \oplus s$的输出值不同的概率至少为$2 ^ {1 - m}$。在本题的限制下这个概率至少是$\frac{1}{8}$。

$0.02$和$\frac{1}{8}$的差异很大，如果我们随机多次的话，根据Chernoff Bound可以发现我们可以设一个$l$使得如果输出不同的$x$占的比例小于等于$l$，我们可以很确定这个$x$对应一个异或和为0的集合。我最快的代码是测试100次，并设$l = 2$（也就是我前面给出的“用时更短的代码”），但是这样错误率我没法保证，更加安全的参数是测试200次，并设$l = 4$（也就是我前面给出的第一份代码），这样错误率至多0.3%（这是通过Chernoff Bound和Union Bound给出的粗浅的上界）。测试1000次，并设$l = 20$，不batching也可以通过，这个的错误率至多在$10 ^ {-23}$级别（这比现代CPU出现软性错误的概率还低若干个数量级，也就是说你更有可能因为硬件原因出错而不是算法本身）。

这个$l$可以设得保守一些，因为接下来你将看到我们不能承受将错误的$x$判断成正确，但如果我们将正确的$x$误判成错误，我们只会增加一些计算量。

可以发现，任何有效信息的集合$u$一定满足$u \cdot x = 0$，其中$\cdot$表示按位AND之后1的个数的奇偶性，如果是奇数则值为1，否则为0。如果我们有了足够多的$x$，我们可以列出一个线性方程组，根据线性代数的知识可以发现这个线性方程组的秩一定是$n - m$，所以我们可以找到$m$个线性无关的解，这一定对应着$m$个有效信息。

知道有效信息之后计算$h$就很简单了，从线性代数的知识可以知道等概率随机一个$x$，那么$x$对应的$m$个有效信息一定也是等概率随机的，于是多次随机对每个结果取多数即可。