UyHiP-2011-Nov
居然自己做出来了所以说还是很简单的 23333
Problem
定义布尔的乘运算为 AND ，加运算为 OR 。定义一个 DNF （析取范式）为一个布尔函数，返回值为若干个若干个变量的积的和，例如 \(f(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3\) 即为一 DNF 。注意这里定义的 DNF 没有 NOT 。
定义一个对称函数为：接受若干个布尔量，返回一个布尔量，且参数的顺序与返回值是无关的。例如 \(f(x_1, x_2) = x_1 x_2\) 即为一对称函数。
我们说一个函数 A 能用另一个函数 B 表达，当且仅当存在一组参数列表之间的对应关系 \(y_1 = x_{a_1}, y_2 = x_{a_2}, \dots, y_m = x_{a_m}\) ，使得 \(A(x_1, x_2, \dots, x_n) = B(y_1, y_2, \dots, y_m)\) 。例如函数 \(A(x_1, x_2, x_3)\) 表示求 \(x_1, x_2, x_3\) 的众数，可以得到 \(A(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3 + x_3 x_1\) ，令 \(B(x_1, x_2, x_3, x_4, x_5, x_6) = x_1 x_2 + x_3 x_4 + x_5 x_6\) ，可以知道 A 能被 B 表达。
现在有两个问题：
- 对于所有的 DNF ，都可以找到一个对称函数使得其能表达这个 DNF ？
- 对于所有的对称函数，都可以找到一个 DNF 使得其能表达这个对称函数？
题目似乎很绕……→_→
Solution
考虑任意一个对称函数，由于参数顺序是无关的，所以对于这个对称函数我们只关心它的参数中有多少个 1 有多少个 0 。换而言之，一个对称函数 A 等价于一个二元函数 \(f(a, b)\) ，其中 \(a\) 表示参数中 1 的个数， \(b\) 表示参数 0 的个数。
再考虑一个 DNF 。可以发现 DNF 的值不会随变量的递增而递减，也就是说对于两组参数 \(x_1, x_2, \dots, x_n\) 和 \(y_1, y_2, \dots, y_n\) ，如果满足 \(f(x_1, x_2, \dots, x_n) = 1\) 且 \(x_1 \leq y_1, x_2 \leq y_2, \dots, x_n \leq y_n\) ，则一定有 \(f(y_1, y_2, \dots, y_n = 1\) 。
所以 DNF 能表达的函数就少得多，考虑一个简单的对称函数 \(f(x)\) 表示 NOT x ，可以发现 \(f\) 是递减的，用 DNF 就表达不出来。所以问题二是错的，上面说的 \(f\) 就是个反例。
而对于任意一个 DNF ，所有不同的参数列表是有限的。假设一个 DNF 有 \(n\) 个参数，则有 \(2^n\) 中不同的参数列表。考虑一个二元非布尔函数 \(f(a, b)\) 保证 \(a + b= 2^n\) 。那么 \(f\) 就可以完整的表达整个 DNF ：我们对 DNF 的 \(n\) 个参数进行二进制编码，可以确定一个 \([0, 2^n)\) 之间的数作为 \(a\) ， \(f\) 根据输入的 \(a\) 的即可返回答案。具体如何进行编码呢？我们让 \(x_i\) 出现的 \(2^{i - 1}\) 次即可。举个例子，一个 DNF \(A(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3\) ，我们构造的对应方式即为 \(B(x_1, x_2, x_2, x_3, x_3, x_3, x_3)\) ，可以知道，一定存在一个 B 使得 B 能够表达出 A 。
nonsense
明天早上要去深圳。不能太坑队友了是不，所以可能暂时不会更新了 →_→