我比较弱看了半天范爷的算法都没太懂……我来讲点奇怪的算法……感觉本质上跟范爷的算法是一样的。

考虑两个布尔变量 $a, b$ 的异或： $a \xor b$。看起来就让人浑身难受，所以我们用 $1$ 表示布尔值 $0$，用 $-1$ 表示布尔值 $1$。也就是用 $(-1)^x$ 代替原来的布尔变量 $x$，这样 $a \xor b = ab$ 了，即 $a$ 和 $b$ 相乘。

不过，线性代数方面什么 $\mathbf{v} \cdot \mathbf{u}$ 和 $\mathbf{v} + \mathbf{u}$ 还是按布尔变量定义更好。$\and$ 是乘法，$\xor$ 是加法，返回值看作 $0$ 和 $1$。

考虑题目中给的函数，我们可以看作 $f: \{1, -1\}^n \mapsto \{1, -1\}$ 的函数。任意这样的函数一定能写成如下形式：

\begin{equation} f(x_1, \dots, x_n) = \sum_{A \subseteq \{1, \dots, n\}} f_A \prod_{k \in A} x_k \end{equation}

$f_A$ 是个系数。

举个例子来说， $\bitnot (x_1 \and x_2) = -\frac{1}{2} - \frac{1}{2}x_1 - \frac{1}{2}x_2 + \frac{1}{2}x_1 x_2$。

这样的话，假设我们想从中提取含 $x_1$ 的项单独成为函数怎么办呢？设：

\begin{equation} f_1(x_1, \dots, x_n) = \frac{f(x_1, \dots, x_n) - f(-x_1, \dots, x_n)}{2} \end{equation}

你会发现不含 $x_1$ 的项被消掉了，含 $x_1$ 的项被保留了。同理：

\begin{equation} f_{-1}(x_1, \dots, x_n) = \frac{f(x_1, \dots, x_n) + f(-x_1, \dots, x_n)}{2} \end{equation}

这样会留下所有不含 $x_1$ 的项。

利用这个方法，我任意给一个 $A$，你都可以用这个方法求出 $f_A$。（即一个个限制 $A$ 中元素在，限制不在 $A$ 中的元素不在。）。直接上当然是 $2^n$ 的，我们考虑每个函数值对答案的贡献，可以发现，假设要求 $f_A$，我们把每个元素是否在 $A$ 中写成向量 $\mathbf{v}$，那么：

\begin{equation} f_A = \frac{1}{2^n} \sum_{\mathbf{x}} f(\mathbf{x}) (-1)^{\mathbf{v} \cdot \mathbf{x}} \end{equation}

我们可以随机抽样很多个 $\mathbf{x}$ 来获得 $f_A$ 的一个近似值。

现在考虑原问题，显然噪声的分量的系数比较小，而系数较大的分量就是题目中的 $z$ 张成的线性空间，大约有 $2^m$ 个。我们就是要提取出 $m$ 个系数值很大的线性无关分量然后随机抽样求出函数 $h$。

错误的算法

考虑随机一个向量 $\mathbf{v}$，它与一个非零分量的点积为 $1$ 的概率有多少？答案是 $\frac{1}{2}$。如果已知与另一个非零分量的点积，与这个非零分量的点积为 $1$ 的概率有多少？答案还是 $\frac{1}{2}$。

我们可以随机多个线性无关的 $\mathbf{v}$，然后他们各与一些分量点积为 $1$。考虑这些 $\mathbf{v}$ 张成的线性空间，就有很大概率有一个向量与其中恰好一个系数很大的分量点积为 $1$，此时就很开心了。

那么怎样提取出来呢？考虑 $\frac{f(\mathbf{x}) - f(\mathbf{x} + \mathbf{v})}{2}$，其中 $\mathbf{x}$ 和 $\mathbf{v}$ 都是向量，你会发现会恰好去掉那些点积与 $\mathbf{v}$ 为 $0$ 的分量。（因为加上 $\mathbf{v}$ 相当于反转对应位）。

所以你就随机一些 $\mathbf{v}$ 然后在张成的线性空间中枚举向量并提取分量，运气好就会抓到恰好一个系数大的分量，然后尝试把每个变量取反看返回值是否变化，变化就说明在分量中，否则不在。这样就找出了分量，然后求这个分量的系数看看大不大，如果大就赶紧收集起来就行了。

代码：http://uoj.ac/submission/8150

UPD：这是个伪证。因为如果知道两个向量跟 $\mathbf{v}$ 的点积之后，再来一个向量我有可能可以推断出跟 $\mathbf{v}$ 的点积是多少，所以这个算法跪了。但是为什么 AC 了呢？这是因为我算法嘴巴上是这样，写出来却一不小心写成了另一个样子，然后恰好是正确的……= =……具体见下面吧。

帅气的算法

还是照旧：考虑 $\frac{f(\mathbf{x}) - f(\mathbf{x} + \mathbf{v})}{2}$，其中 $\mathbf{x}$ 和 $\mathbf{v}$ 都是向量，你会发现会恰好去掉那些点积与 $\mathbf{v}$ 为 $0$ 的分量。然后考虑 $\frac{f(\mathbf{x}) + f(\mathbf{x} + \mathbf{v})}{2}$，其中 $\mathbf{x}$ 和 $\mathbf{v}$ 都是向量，你会发现会恰好去掉那些点积与 $\mathbf{v}$ 为 $1$ 的分量。

首先我们随机出 $s$ 个线性无关的向量 $\mathbf{v}_1, \dots, \mathbf{v}_s$。然后考虑一个向量 $\mathbf{x}$ 跟这 $s$ 个向量的点积，能写成一个 $s$ 维的向量。你可以注意到 $(\mathbf{x} + \mathbf{y}) \cdot \mathbf{v} = \mathbf{x} \cdot \mathbf{v} + \mathbf{y} \cdot \mathbf{v}$，所以我们如果对系数很大的那些分量组成的线性空间中的每个向量都求出所有 $\mathbf{v}$ 的点积写出那个向量，你会发现仍然组成了一个线性空间 $U$。

考虑系数很大的那些分量组成的线性空间中的一组基，如果它们所对应的向量是线性无关的话，那么每个 $U$ 中的向量都唯一对应一个系数很大的分量。于是我们就可以枚举每一个 $U$ 中的向量 $u$，然后用“强制点积为 $0$”、“强制点积为 $1$” 这两种操作来把 $f$ 变成只含 $u$ 所对应的那个分量，再对 $f$ 每一个输入变量反转下带进去看结果是否反转来知道这个分量中究竟含哪些变量。

“如果它们所对应的向量是线性无关的话，那么……” 这个概率看起来跟“在 $s$ 维空间随机 $m$ 个向量，他们线性无关”是一样的（因为这些基线性无关，于是它们之间的点积无法互相推导。所以是独立的？粗略感受下应该是这样）。具体多少我也算不清楚，反正就是灰常大。所以随机个几次 $\mathbf{v}_1, \dots, \mathbf{v}_s$ 的话，这题就这么愉快地解决啦～（这应该就是fhq的算法了……）

http://uoj.ac/submission/8344

那么我原来写的什么呢？我相当于只找到那个 $U$ 中每一位都是 $1$ 的那个向量囧……太sb了……